11、爬台阶 ——递归方法

有一个n层的楼梯，你一次可以爬1层或者2层，请问有多少种爬楼梯的方法？ 要求输入n，输出方法的数量

#include
int sum(int n){
	if(n==1){
		return 1;
	}
	if(n==2){
		return 2;
	}
	return sum(n-1)+sum(n-2);	
}
int main()
{
	int n;
	scanf("%d",&n);
	printf("%d级台阶有%d种方法",n,sum(n));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

12、两数之和

给定一个整数列表 nums 和一个整数目标值 target，请你在该列表中找出和为目标值 target 的那两个整数，并返回它们的列表下标。
你可以假设每种输入只会对应一个答案。但是，列表中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
未解决：没能实现输入一组数组。

#include

int main()
{
	int nums[1000],target,n=0;
	while((scanf("%d",&nums[n])!=EOF){
		n++;
	}
	target=nums[n];
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			if(nums[i]+nums[j]==target){
				printf("%d=%d+%d",target,nums[i],nums[j]);
			}
		}
	} 
	
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

13、无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路：遍历。记录每次不重复的第一个字符下标p，从p开始到第i个依次判断是否和第i个字符相等，找到后记录新的p,并得到新的最大长度。
字符串处理#include。获得字符串长度strlen(s)

#include
#include
int max(int a,int b){
    return a>b?a:b;
}

int maxlength(char * s){
    int len=strlen(s);
    if(len<2)return len;
    int m=1,ch=s[0],p=0;
    for(int i=1;i<len;i++){
        for(int j=p;j<i;j++){//p是上一个判断相同的字符下标。 
            if(s[j]==s[i]){//这里从p开始往后依次和第i个字符判断是否相同。 
                m=max(m,i-p);//两个相同字符下标之差就是本次找到的无重复字符串长度 
                p=j+1;
            }
        }
    }
    m=max(m,len-p);
    return m;
}
int main()
{
	char s[1000],k[1000];
	scanf("%s",&s);
	int max;
	max=maxlength(s);
	printf("%d",max);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

14、整数解

求满足表达式 A+B=C 的所有整数解，其中 A,B,C 都为 1~3 之间的数。
思路：直接遍历

#include
int main()
{
	int a,b,c;
	for(a=1;a<=3;a++){
		for(b=1;b<=3;b++){
			for(c=1;c<=3;c++){
				if(a+b==c){
					printf("%d+%d=%d\n",a,b,c);
				}
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

15、巧妙填数

题干
将 1~9 这 9 个数字填入九个空格中，每一横行的三个数字组成一个三位数，如果要使第二行的三位数是第一行的 2 倍，第三行的三位数是第一行的 3 倍，应该怎么填，请用编程列举出所有解。例如：

思路：把每一行看成1个3位数，然后再拆开。
9个数字不重复，且倍数关系限制了第一行的取值范围：123-329。再此范围内遍历，得到9个数的取值，再判断是否重复，不重复即满足条件，输出结果。

#include
//判断这9个数字是否有重复 
bool isnotsame(int x[]){
	for(int i=0;i<9;i++){
		for(int j=i+1;j<9;j++){
			if(x[i]==x[j]){
				return false;
			}
		}
	}
	return true;
}
int main()
{
	int flag[9],one,two,three;
	//不重复的3位数最小123，最大987，但第3行是第1行3倍，所以第1行最大不超过329 
	for(one=123;one<=329;one++){
		two=one*2;
		three=one*3;
		//得到9个数字，存入数组flag中。 
		flag[0]=one/100;flag[1]=(one-flag[0]*100)/10;flag[2]=one%10;
		flag[3]=two/100;flag[4]=(two-flag[3]*100)/10;flag[5]=two%10;
		flag[6]=three/100;flag[7]=(three-flag[6]*100)/10;flag[8]=three%10;
		
		if(isnotsame(flag)){
			for(int k=0;k<9;k++){
				for(int m=0;m<3;m++){
					printf("%d ",flag[k++]);
				}
				k--;
				printf("\n");	
			}
			printf("\n");
		}
		
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

16、古纸残篇

在一位数学家的藏书中夹有这一张古旧的纸片，纸片上的字早已模糊不清了，只留下曾经写过字的痕迹，依稀还可以看出它是一个乘法算式，这个算式上原来的数字是什么呢？夹着这张纸片的书页上，“素数”两个字被醒目的划了出来，难道说，这个算式与素数有什么关系吗？有人对此作了深入的研究，果然发现这个算式中的每一个数字都是素数，而且这样的算式是唯一的。请你用编程找出这个算式。

定义并初始化数组：int str[4]={2,3,5,7}

#include
#include
bool issushu(int n){
	if(n==2||n==3||n==5||n==7){
		return true;
	}
	return false;
}

int main()
{
	int a,b,c,d,e,str[4]={2,3,5,7},r[13],flag;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int t=0;t<4;t++){
					for(int s=0;s<4;s++){
						flag=0;
						a=str[i]*100+str[j]*10+str[k];
						b=str[t]*10+str[s];
						c=a*b;
						d=a*str[t];
						e=a*str[s];
						r[0]=d/1000;r[1]=d%1000/100;r[2]=d%1000%100/10;r[3]=d%10;
						r[4]=e/1000;r[5]=e%1000/100;r[6]=e%1000%100/10;r[7]=e%10;
						r[8]=c/10000;r[9]=c%10000/1000;r[10]=c%10000%1000/10;r[11]=c%10000%1000%100/10;r[12]=c%10;
						
						for(int x=0;x<13;x++){
							if(issushu(r[x])){
								flag++;
							}
							
						}
						if(flag==13){
							printf("%d*%d\n",a,b);
						}
						
					}
				}
			}
		}
	} 
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

17、求质数个数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量
思路：直接遍历。

#include
#include
bool issushu(int n){
	for(int j=2;j<n;j++){
		if(n%j==0){
			return false;
		}
	}
	return true;
}

int main()
{
	int n,num=0;
	scanf("%d",&n);
	for(int i=2;i<n;i++){
		if(issushu(i)){
			num++;
		}
	}
	printf("小于%d的质数有%d个",n,num);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

18、最小公倍数

给定两个数，求出他们的最小公倍数。
思路：递归求公因数，两数乘积÷最大公因数=最小公倍数。

#include

int gongyin(int x,int y){
	if(x%y==0){
		return y;
	}
	int t;
	t=x%y;
	x=y;y=t;//让第一个数>第二个数
	return(x,y); 
}

int main()
{
	int m,n,s;
	printf("输入第一个数字：");
	scanf("%d",&m);
	printf("输入第一个数字：");
	scanf("%d",&n);
	if(m<n){
		s=m,m=n,n=s;
	}
	printf("%d和%d的最小公倍数为：%d",m,n,m*n/gongyin(m,n));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

19、爱因斯谜题

一条街上有 5 栋房子，刷不同的漆，住不同国的人，喝不同饮料，抽不同烟，养不同的宠物。。

很复杂，听说下面这样可以解决，待会来看看

define maxn 6
int color[maxn];
int animal[maxn];
int nationality[maxn];
int drink[maxn];
int smoke[maxn];
int used[maxn][maxn];
int find(int *list,int key){
int i;
for (i=1;i<=5;i++){
if (list==key) return i;
}
return 0;
}
void out(int *list){
int i;
for (i=1;i<=5;i++){
printf(“%d “,list);
}
printf(“\n”);
}

int check(){
// goto loop;
if (drink[3]!=3) return 0;

if (find(drink,1)!=find(nationality,3)) return 0;
if (find(color,2)!=find(drink,2)) return 0;
if (find(smoke,1)!=find(animal,2)) return 0;
if (find(color,5)!=find(smoke,2)) return 0;
if (abs(find(smoke,4)-find(animal,3))!=1) return 0;
if (abs(find(animal,4)-find(smoke,2))!=1) return 0;
if (drink[find(smoke,3)]!=4) return 0;
if (smoke[find(nationality,4)]!=5) return 0;
if (abs(find(smoke,4)-find(drink,5))!=1) return 0;
//loop:
out(color);
out(nationality);
out(animal);
out(drink);
out(smoke);
printf(“\n”);
exit(0);
return 1;
}

void dfs(int step,int *list,int count){
if (count==3 && nationality[1]!=5) return;
if (count==3 && find(color,1)!=find(nationality,1)) return;
if (count==4 && find(nationality,2)!=find(animal,1)) return;
if (count==2 && find(color,2)+1!=find(color,3)) return;
if (count==3 && abs(find(color,4)-find(nationality,5))!=1) return;

int i;
if (step==6){
switch(count){
case 1:dfs(1,nationality,count+1);
case 2:dfs(1,animal,count+1);
case 3:dfs(1,drink,count+1);
case 4:dfs(1,smoke,count+1);
case 5:check();
}
return;
}
for (i=1;i<=5;i++){
if (used[count]) continue;
list[step]=i;
used[count]=1;
dfs(step+1,list,count);
used[count]=0;
}
}
int main(){
freopen(“output.txt”,”w”,stdout);
dfs(1,color,1);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

https://www.xuebuyuan.com/953524.html

20、台阶问题

有一条很长的楼梯，若每步跨 2 阶，则最后剩 1 阶；若每步跨 3 阶，则最后剩 2 阶；若每步跨 5 阶，则最后剩 4 阶；若每步跨 6 阶，则最后剩 5阶；若每步跨 7 阶，最后能刚好一阶不剩。请问这个楼梯至少有多少台阶
思路：没有给定范围，用while循环，循环中满足条件就输出并跳出循环。

#include

int main()
{
	int n=7;
	while(n++){
		if(n%2==1&&n%3==2&&n%5==4&&n%6==5&&n%7==0){
			printf("这个楼梯至少有%d个台阶。",n);
			return 0;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13