算法考试填数字问题

在算法考试中的最后一题,题目为:对于任意一个数字n,我们有一个长度为2n的数组,我们需要把1~n个数填入这个数组里2次。填入数字的规则如下:当填入数字n时,另一个n必须与当前的n距离为n,例如两个1之间要夹着一个数字,两个2之间要夹着两个数字,如此类推,直到把2n个空格填满。现在我们要设计一个算法,我们求出n个数字的所有排列方式。 我的算法思想如下:既然两个n之间的距离为n,我们应该从n开始填入,因为n可以填入的位置最少,为1~n-1,而当n填入数组之后,n-1可以选择填入的位置的个数也为n-1,如此类推,1可以填入的位置的个数也为n-1。讲到这里,大家应该我所采用的算法就是深度遍历树,就像遍历一个文件夹里所有的文件一样。废话不多说,下面贴代码。 #include<iostream> using namespace std; int *array=NULL; int size=0; void input(int n); void output(); //初始化数组里面不大于n的位置 void init(int * a,int n){ for(int i=0;i<size;i++) { if(a[i]<=n) a[i]=0; } } int main(){ cout<<"please input your number:"<<endl; int n; cin>>n; size=2*n; array=new int[size]; init(array,n); input(n); //output(); } //往数组里面填入数字n,begin为允许开始填入的位置 void input(int n){ if(n==0) return; for(int i=0;i<size-n-1;i++){ init(array,n); if(array[i]==0&&array[i+n+1]==0){ array[i]=n; array[i+n+1]=n; if(n==1) { output(); } input(n-1); }else continue; } } } void output(){ cout<<"output the array:"<<endl; for(int i=0;i<size;i++){ cout<<array[i]<<"\t"; } cout<<endl; } 算法正确性我还没检验,请各位大神指正。最后放下代码下载地址:http://download.csdn.net/detail/xanxus46/4597909

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

1023
来自专栏分布式系统和大数据处理

正则表达式教程

1095
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

862
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

711
来自专栏静默虚空的博客

排序算法系列

概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问...

2347
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1934
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

4086
来自专栏Java技术栈

神奇,教你用随机数打印hello world

下面是一段随机数程序。 public static void main(String[] args) { System.out.println(rand...

3695
来自专栏技术杂谈

给出一组非负整数,重新排序组成最大的数

先把对比的数字转成字符,拼接后再转成整数进行大小对比,即 int(a+b) 与 int(b+a) 进行降序排列。代码1。

6158
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1993

扫码关注云+社区

领取腾讯云代金券