首页 > 代码库 > 实习题

实习题

数学题(前两问用数学方法实现)

1. 找出这种4位数:千位数等于4位数中0的个数,百位数等于4位数中1的个数。十位数等于4位数中2的个数,个位数等于4位数中3的个数。

2. 改为7位数。最高位为0的个数,次高位为1的个数,依次类推,结果又怎样?

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


解:

1.如果这个四位数是:

千位

百位

十位

个位

A

B

C

D

由于总共仅仅有4位。所以ABCD的值都小于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满足条件

故,总共同拥有两个四位数满足条件,分别为:12102020

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("\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);
}
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)



实习题