1. 找出这种4位数：千位数等于4位数中0的个数，百位数等于4位数中1的个数。十位数等于4位数中2的个数，个位数等于4位数中3的个数。
2. 改为7位数。最高位为0的个数，次高位为1的个数，依次类推，结果又怎样？
3. 编程实现一个函数，求出位数为n时的解，要求算法复杂度尽可能小。
解：
1.如果这个四位数是：
|
千位 |
百位 |
十位 |
个位 |
|
A |
B |
C |
D |
由于总共仅仅有4位。所以A、B、C、D的值都小于4。即：
0<=A,B,C,D<=4 (1)
4位数中的各位分别统计0,1,2,3的个数。因此各位相加的和一定为4。即：
A+B+C+D=4 (2)
同一时候发现，若D=1，则有一个数出现了3次，若C=1，则有一个数出现了2次，依次类推。然而总出现次数还是要满足它的位数。由此我们能够得出另外一个公式：
0*A+1*B+2*C+3*D=4 (3)
由(1)、(2)、(3)给出的限制条件，我们能够推导出满足要求的四位数：
当A=3时：
B+C+D=4
B+2C+3D=4
显然没有满足条件的解。
当A=2时：
B+C+D=2
B+2C+3D=4
得到：B=0， C=2， D=0 2020满足条件
当A=1时：
B+C+D=3
B+2C+3D=4
得到：B=2。 C=1， D=0 1210满足条件
故，总共同拥有两个四位数满足条件，分别为：1210、2020
2.假设为一个7位数
|
A |
B |
C |
D |
E |
F |
G |
採用迭代的方式求解。循环统计并更新相应位上数字出现的次数。设定起始的7位数为：
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
第1次迭代：
(1)统计0出现的次数为：7。马上更新：
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
(2)依次统计1,2,3,4,5,6出现的次数都为：0。
第1次迭代后的结果：
|
7 |
0 |
0 |
0 |
0 |
0 |
0 |
第2次迭代：
|
6 |
0 |
0 |
0 |
0 |
0 |
0 |
(1)统计0出现的次数为：6，马上更新：
|
6 |
0 |
0 |
0 |
0 |
0 |
0 |
(2)统计1,2,3,4,5出现的数都为：0。
(3)统计6出现的次数为：1，马上更新：
|
6 |
0 |
0 |
0 |
0 |
0 |
1 |
第2次迭代的结果：
|
6 |
0 |
0 |
0 |
0 |
0 |
1 |
第3次迭代：
(1)
|
5 |
0 |
0 |
0 |
0 |
0 |
1 |
(2)
|
5 |
1 |
0 |
0 |
0 |
0 |
1 |
(3)
|
5 |
1 |
0 |
0 |
0 |
1 |
1 |
(4)
|
5 |
1 |
0 |
0 |
0 |
1 |
0 |
第4次迭代：
|
4 |
2 |
1 |
0 |
1 |
0 |
0 |
第5次迭代：
|
3 |
2 |
1 |
1 |
0 |
0 |
0 |
第6次迭代：
|
3 |
2 |
1 |
1 |
0 |
0 |
0 |
迭代到第六次的时候它的值与第5次的结果同样。
【代码】
C语言版：
int match(int *arr, int n)
{
int i, j, cout;
for(i = 0; i < n; i++)
{
cout = 0;
for(j = 0; j < n; j++)
if (arr[j] == i)
cout++;
if(cout != arr[i])
return 0;
}
return 1;
}
int isbond(int *arr, int n)
{
int i, cout1, cout2;
cout1 = cout2 = 0;
for(i = 0; i < n; i++)
{
cout1 += arr[i];
cout2 += i*arr[i];
}
if(cout1 <= n && cout2 <= n)
return 1;
else
return 0;
}
void recfun(int *arr, int n, int i)
{
int j, k;
if(i == -1)
{
if(match(arr, n) == 1)
{
for(j = 0; j < n; j ++)
printf("%d ", arr[j]);
printf("
");
}
return;
}
for(k = (n-1); k >= 0; k--)
{
arr[i] = k;
if(isbond(arr, n) == 1)
recfun(arr, n, i-1);
}
}
void fun(int n)
{
int i;
int *arr;
arr = (int *)malloc(n * sizeof(int)); //动态分配内存
for(i = 0; i < n; i++)
arr[i] = 0; //初始化
recfun(arr, n, n-1);
}Python版：
# -*- coding:utf-8 -*-
"""
@author: Liu Jietang
@e-mail: liujietang126@163.com
找出满足条件的数
採用递归搜索
"""
def isbond(arr, n):
cout1 = 0
cout2 = 0
for i in range(n):
cout1 += arr[i]
cout2 += i*arr[i]
if cout1 <= n and cout2 <= n:
return True
else:
return False
def ismatch(arr, n):
for i in range(n):
cout = 0
for j in range(n):
if arr[j] == i:
cout += 1
if cout != arr[i]:
return False
return True
def recursion(arr, n, i):
if i == -1:
if ismatch(arr, n):
print arr
return
for k in range(n-1, -1, -1):
arr[i] = k
if isbond(arr, n):
recursion(arr, n, i-1)
def fun(n =10):
arr = [0]*n
recursion(arr, n, n-1)
if __name__ == "__main__":
n = int(raw_input("Please input the digits of the number(1~10)："))
fun(n)