- 注册时间
- 2008-9-9
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 3282
- 在线时间
- 小时
|
发表于 2008-9-9 15:24:44
|
显示全部楼层
第一种是最笨的方法:把每一位从0到9都尝试过,然后再次统计这个数组得到另外一个结果,如果两个数组相等就表明成功,否则就失败。但是这个方法算法太耗时间,不推荐,如果面试的时候能够讲出这种方法,估计面试官还是会给一点分的!
第二种:因为总共出现的总次数为10,所以我们可以很有效的利用这个属性,进行一次排列,为了分析简单,我们从最大开始:
9+1+n*0(n=8),对这个数据进行整理得8100000001,再次对这个数组进行统计分析得7200000010,与刚得到的数组不一样,错误,转到下一个排列
8+2+n*0(n=8),对这个数据进行整理得8010000010,再次对这个数组进行统计分析得7200000010,与刚得到的数组不一样,错误,转到下一个排列
8+1+1+n*0(n=7),对这个数据进行整理得7200000010,再次对这个数组进行统计分析得7110000100,与刚得到的数组不一样,错误,转到下一个排列
....
总共的排列数:
9 1 0 0 0 0 0 0 0 0
8 2 0 0 0 0 0 0 0 0
8 1 1 0 0 0 0 0 0 0
7 3 0 0 0 0 0 0 0 0
7 2 1 0 0 0 0 0 0 0
7 1 1 1 0 0 0 0 0 0
6 4 0 0 0 0 0 0 0 0
6 3 1 0 0 0 0 0 0 0
6 2 2 0 0 0 0 0 0 0
6 2 1 1 0 0 0 0 0 0
6 1 1 1 1 0 0 0 0 0
5 5 0 0 0 0 0 0 0 0
5 4 1 0 0 0 0 0 0 0
5 3 2 0 0 0 0 0 0 0
5 3 1 1 0 0 0 0 0 0
5 2 2 1 0 0 0 0 0 0
5 2 1 1 1 0 0 0 0 0
5 1 1 1 1 1 0 0 0 0
4 4 2 0 0 0 0 0 0 0
4 4 1 1 0 0 0 0 0 0
4 3 3 0 0 0 0 0 0 0
4 3 2 1 0 0 0 0 0 0
4 3 1 1 1 0 0 0 0 0
4 2 2 2 0 0 0 0 0 0
4 2 2 1 1 0 0 0 0 0
4 2 1 1 1 1 0 0 0 0
4 1 1 1 1 1 1 0 0 0
3 3 3 1 0 0 0 0 0 0
3 3 2 2 0 0 0 0 0 0
3 3 2 1 1 0 0 0 0 0
3 3 1 1 1 1 0 0 0 0
3 2 2 2 1 0 0 0 0 0
3 2 2 1 1 1 0 0 0 0
3 2 1 1 1 1 1 0 0 0
3 1 1 1 1 1 1 1 0 0
2 2 2 2 2 0 0 0 0 0
2 2 2 2 1 1 0 0 0 0
2 2 2 1 1 1 1 0 0 0
2 2 1 1 1 1 1 1 0 0
2 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
也就是说,对这个数据无论进行过多少次统计,它的值都还是等于原值的排列,才是正确的排列
算法如下:(没有注释及缩进的算法,见笑了*^_^*)
(且这个程序必须假定A数组为初始值0增量1的等差数列)- C/C++ code
- #include <iostream>
-
- using namespace std;
-
- const int N = 10;
- int source[N];
- int dest[N] = {0};
- int dest2[N] = {0};
-
- void init()
- {
- for(int i=0; i<N; i++)
- {
- source[i] = i;
- }
- }
-
- void display(int target[])
- {
- for(int i=0; i<N; i++)
- {
- printf("%4d", target[i]);
- }
- cout << endl;
- }
-
- /*
- 从src的数据统计出现的次数并存入dest中
- Create by Denny, Email: [email]silitex@yeah.net[/email]
- */
- void count(int *dest, int *src)
- {
- int i;
-
- for (i = 0; i < N; i++) // dest清0
- dest[i] = 0;
- for (i = 0; i < N; i++) // 整理当前的数值到正确的位置上
- dest[src[i]]++;
- }
-
- void main()
- {
- init();
- display(source); // 原始数组
-
- int tmp[N] = {N-1}; // 默认给第一个赋值为N-1
- int posi = 0;
- while (posi >= 0)
- {
- int i = 0;
- int leave = N;
- int min = tmp[0];
- for (; i <= posi; i++)
- {
- leave -= tmp[i];
- if (tmp[i] < min)
- min = tmp[i];
- }
- for (; i < N; i++)
- tmp[i] = 0;
- while (leave > 0)
- {
- if (min > leave)
- min = leave;
- tmp[++posi] = min;
- leave -= min;
- }
-
- count(dest, tmp); // 初步统计,得到一个正确的数值
- count(dest2, dest); // 再次进行统计
- for (i = 0; i < N; i++) // 核对结果
- if (dest2[i] != dest[i])
- break;
- if (i >= N) // 正确结果,显示答案
- display(dest);
-
- while (--tmp[posi] == 0)
- posi--;
- }
- }
复制代码 得到10位数的答案有且仅有一个:
6 2 1 0 0 0 1 0 0 0
9位数答案(只有一个):
5 2 1 0 0 1 0 0 0
8位数答案(只有一个):
4 2 1 0 1 0 0 0
7位数答案(只有一个):
3 2 1 1 0 0 0
6位数无解
5位数答案(只有一个):
2 1 2 0 0
4位数答案:
2 0 2 0
1 2 1 0
3位数无解
2位数无解
1位数无解
11位数答案(只有一个):
7 2 1 0 0 0 0 1 0 0 0
12位数答案(只有一个):
8 2 1 0 0 0 0 0 1 0 0 0
13位数答案(只有一个):
9 2 1 0 0 0 0 0 0 1 0 0 0
14位数答案(只有一个):
10 2 1 0 0 0 0 0 0 0 1 0 0 0
15位数答案(只有一个):
11 2 1 0 0 0 0 0 0 0 0 1 0 0 0
16位数答案(只有一个):
12 2 1 0 0 0 0 0 0 0 0 0 1 0 0 0 |
|