深圳睿初科技实习题

1. 找出这样的4位数：千位数等于4位数中0的个数，百位数等于4位数中1的个数，十位数等于4位数中2的个数，个位数等于4位数中3的个数。

2. 改为7位数，最高位为0的个数，次高位为1的个数，依次类推，结果又如何？

3. 编程实现一个函数，求出位数为n时的解，要求算法复杂度尽可能小。

解：

1.假设这个四位数是：

因为总共只有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位数

采用迭代的方式求解，循环统计并更新对应位上数字出现的次数。设定起始的7位数为：

第1次迭代：

(1)统计0出现的次数为：7，立即更新：

(2)依次统计1,2,3,4,5,6出现的次数都为：0。

第1次迭代后的结果：

第2次迭代：

(1)统计0出现的次数为：6，立即更新：

 (2)统计1,2,3,4,5出现的数都为：0。

(3)统计6出现的次数为：1，立即更新：

第2次迭代的结果：

第3次迭代：

 (1)

(2)

(3)

(4)

第4次迭代：

第5次迭代：

第6次迭代：

迭代到第六次的时候它的值与第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("\n");
		}
		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);
}

# -*- 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)

深圳睿初科技实习题,布布扣,bubuko.com

深圳睿初科技实习题

原文：http://blog.csdn.net/jjjcainiao/article/details/32732023