silitex 发表于 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，与刚得到的数组不一样，错误，转到下一个排列
....
总共的排列数：
9100000000
8200000000
8110000000
7300000000
7210000000
7111000000
6400000000
6310000000
6220000000
6211000000
6111100000
5500000000
5410000000
5320000000
5311000000
5221000000
5211100000
5111110000
4420000000
4411000000
4330000000
4321000000
4311100000
4222000000
4221100000
4211110000
4111111000
3331000000
3322000000
3321100000
3311110000
3222100000
3221110000
3211111000
3111111100
2222200000
2222110000
2221111000
2211111100
2111111110
1111111111
也就是说，对这个数据无论进行过多少次统计，它的值都还是等于原值的排列，才是正确的排列
算法如下：（没有注释及缩进的算法，见笑了*^_^*）
（且这个程序必须假定A数组为初始值0增量1的等差数列）C/C++ code
#include <iostream>

using namespace std;

const int N = 10;
int source;
int dest = {0};
int dest2 = {0};

void init()
{
    for(int i=0; i<N; i++)
    {
      source = i;
    }
}

void display(int target[])
{
    for(int i=0; i<N; i++)
    {
      printf("%4d", target);
    }
    cout << endl;
}

/*
    从src的数据统计出现的次数并存入dest中
    Create by Denny, Email: silitex@yeah.net
*/
void count(int *dest, int *src)
{
    int i;

    for (i = 0; i < N; i++)    // dest清0
      dest = 0;
    for (i = 0; i < N; i++)    // 整理当前的数值到正确的位置上
      dest]++;
}

void main()
{
    init();
    display(source);    // 原始数组

    int tmp = {N-1};    // 默认给第一个赋值为N-1
    int posi = 0;
    while (posi >= 0)
    {
      int i = 0;
      int leave = N;
      int min = tmp;
      for (; i <= posi; i++)
      {
            leave -= tmp;
            if (tmp < min)
                min = tmp;
      }
      for (; i < N; i++)
            tmp = 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 != dest)
                break;
      if (i >= N)            // 正确结果，显示答案
            display(dest);

      while (--tmp == 0)
            posi--;
    }
}得到10位数的答案有且仅有一个：
6210001000
9位数答案（只有一个）：
521001000
8位数答案（只有一个）：
42101000
7位数答案（只有一个）：
3211000
6位数无解
5位数答案（只有一个）：
21200
4位数答案：
2020
1210
3位数无解
2位数无解
1位数无解
11位数答案（只有一个）：
72100001000
12位数答案（只有一个）：
821000001000
13位数答案（只有一个）：
9210000001000
14位数答案（只有一个）：
102100000001000
15位数答案（只有一个）：
1121000000001000
16位数答案（只有一个）：
12210000000001000

manthanein 发表于 2017-1-21 12:14:34

http://oeis.org/search?q=21200&language=english&go=Search

manthanein 发表于 2017-1-21 12:15:49

https://en.wikipedia.org/wiki/Self-descriptive_number

manthanein 发表于 2017-1-21 12:16:41

http://oeis.org/A046043
http://oeis.org/A138480
页: 1 [2]
查看完整版本: 发现一很有趣的题目，讨论一下吧