第四周习题

习题"/>

第四周习题

习题

• 1、字符识别
• • 代码
  • • 个人理解
• 2、数的划分
• • 理解
  • • 代码
• 3、幸运人士
• • 代码
  • • 理解
• 4、线性查找
• • 理解
  • • 代码
• 5、二分查找（递归）
• • 理解
  • • 代码：
• 6、二分查找（非递归）
• • 代码

1、字符识别

题目描述

• 你的任务是写一个程序进行字符识别。别担心，你只需要识别1, 2, 3，如下：

.*.  ***  *** 
.*.  ..*  ..* 
.*.  ***  *** 
.*.  *..  ..* 
.*.  ***  *** 

输入

• 输入仅包含一组数据，由6行组成。第一行为字符的个数n（1<=n<=10）。以下5行每行包含4n个字符。每个字符恰好占5行3列，然后是一个空列（用"."填充）。

输出

• 输出应包含一行，即识别出的各个字符。

样例输入 Copy

3
.*..***.***.
.*....*...*.
.*..***.***.
.*..*.....*.
.*..***.***.

样例输出 Copy

123

这是本人平台测试通过所看到的大佬的文章，如有需要，请点击这里

代码

#include<stdio.h>
#define MAX 100
int main()
{int n,i,k;char str[MAX],s[MAX];while(~scanf("%d",&n)){getchar();for(i=0;i<5;i++){if(i==3)scanf("%s",str);elsescanf("%s",s);}for(i=0;i<n*4;i++){if(str[i]=='*'){if(i%4==1)printf("1");else if(i%4==0)printf("2");else if(i%4==2)printf("3");}}printf("\n");}return 0;
}

【这就是那个文章里的代码哈~】

个人理解

• 区分数字是看竖着的，那区分1和2、3很简单，区分2和3就要看第四行*的位置，然后把第四行拎出来分析，又可以区分出1和2和3，虽然我知道这么做，可是我不知道怎么下手啊，所以我还是去看了别人的代码~

2、数的划分

题目描述

• 使用递归编写一个程序，求一个正整数n的所有划分个数。 例如，输入3，输出3；输入4，输出5。

输入

• 多组输入，每一组是一个正整数n。

输出

• 输出划分数。

样例输入 Copy

3
4

理解

这个题目我们上课就讲过啦，只要发现其中规律就不难啦~

代码

#include<stdio.h>
int cbb(int n,int m){if(m<1||n<1)return 0;else if(m==1||n==1)return 1;else if(m>n)return cbb(n,n);else if(m==n)return cbb(n,m-1)+1;elsereturn cbb(n,m-1)+cbb(n-m,m);
}
int main(){int n,m;while(scanf("%d",&n)!=EOF){m = n;printf("%d\n",cbb(n,m));}
}

3、幸运人士

题目描述

• 一次大型派对的最后节目是选出一位幸运人士，该人士将获得派对组织者准备的一个钻石戒指。 而选择幸运人士的办法是让所有人员一字排列，然后从左至右点数，凡是奇数号的全部剔除。 对于剩下的人员，又从左至右点数，逢奇数号就剔除。
  如此不断递归下去，直到只剩下一个人为止，此人即为幸运之人。 请设计一个递归算法计算幸运之人所在的位置。

输入

• 多组数据，每组输入一个正整数n。

输出

• 输出最后剩下的那个人的位置。

样例输入 Copy

1
2
3

样例输出 Copy

1
2
2

代码

import java.util.Scanner;public class Main {static int h=1;static int sum=0;public void cbb(int n){if(n==1)System.out.println(1);else{while(n>1) {for(int i=1;h<=n;i++) {h=2*h;	        		}n=n/2;sum=h/2;	        		}System.out.println(sum);}}public static void main(String[] args) {// TODO Auto-generated method stubScanner sc=new Scanner(System.in);Main m = new Main();while(sc.hasNext()) {int n=sc.nextInt();m.cbb(n);}}
}

【 我最早看到的那一篇文章找不到了~】

理解

• 说白了，我知道题目让你干嘛，也知道有一个规律，只可意会不可言传，急的我室友专门写了一篇博客讲这个题目的思路以及规律，就是下面的链接哈~

链接：幸运人士–Anna Qiao

4、线性查找

题目描述

• 请编写一个程序，输入包含n（n<=10000）个整数的数列S以及包含q个(q<=500)不重复整数的数列T，输出既包含于T也包含于S的整数的个数C。S、T中的元素均大于0且小于109，T的元素不重复。

输入

• 多组输入。 每一组输入的第一行输入n，第二行输入代表S的n个整数，第三行输入q，第四行输入代表T的q个整数。

输出

• 用1行输出C。

样例输入 Copy

5
1 2 3 4 5
3
3 4 1

样例输出 Copy

3

理解

我的第一反应任然是打开了CSDN，对的，没错，可是我发现我不会C++啊，然后就自己写了，但也算是接住了CSDN别人的博客去理解题目了：利用循环，遇到相等的数值就是计数，然后输出就行

代码

import java.util.Scanner;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int bb[]= new int[1000];while(sc.hasNext()){int n = sc.nextInt();int S[] = new int[n];for(int i=0;i<n;i++)S[i] = sc.nextInt();int q = sc.nextInt();int T[] = new int[q];for(int i=0;i<q;i++)T[i] = sc.nextInt();if(n<=10000&&q<=500){int geshu = 0;for(int i=0;i<q;i++){for(int j=0;j<n;j++){if(T[i]==S[j]){geshu++;}							}}System.out.println(geshu);	}}}}

5、二分查找（递归）

题目描述

• 使用递归算法，实现二分搜索。

输入

• 多组数据输入，每组第一个数字为数组的长度n，然后输入n个整数，最后输入待查询的值。

输出

• 输出待查询值所在的位置，如果没有找到，则返回-1。

样例输入 Copy

3 1 2 3 2
4 0 1 3 4 2 

样例输出 Copy

2
-1

理解

这个我们老师也讲过，就是不断二分，但是编译的过程中，我还是发现自己得不出结果，然后我又打开了CSDN，还是发现运行错误，最后不断改代码，终于，改对了，因为我自己定义数组的长度为100，而后面，输入的第一个数n，也就是即将输入的n个数，数组的长度应该是shuzu[n],但是因为我首先就确定了数组的长度，所以不管我怎么查找，都返回-1，幸好最后改对了，唉_{（表述不准确之处还望海涵）}

下面是我当时看得代码，后面我自己修改了些地方，有需要的记得戳一戳蓝色字体哟！
链接：二分查找算法（递归与非递归两种方式）

代码：

import java.util.Scanner;public class Main {public static int cbb(int[] shuzu, int low, int high, int key) {if (shuzu == null || shuzu.length == 0) {return -1;}int middle = (low + high) / 2;if (low > high) {return -1;}if (shuzu[middle] == key) {return middle+1;//这是我根据题目要求的输出改的，所以大家一定要看清楚题目要求的输出呀} else if (shuzu[middle] > key) {return cbb(shuzu, low, middle - 1, key);} else {return cbb(shuzu, middle + 1, high, key);}}public static void main(String[] args){Scanner sc = new Scanner(System.in);Main main = new Main();while(sc.hasNext()){int n = sc.nextInt();int []shuzu = new int[n];for(int i=0;i<n;i++){shuzu[i]=sc.nextInt();}int key = sc.nextInt();				System.out.println(Main.cbb(shuzu, 0, n-1, key));}}}

6、二分查找（非递归）

代码

import java.util.Scanner;public class Main {public static int cbb(int shuzu[], int key) {int mid = shuzu.length / 2;if (key == shuzu[mid]) {return mid+1;//根据题目要求来的~}int low= 0;int high = shuzu.length - 1;while (low<= high) {mid = (high - low) / 2 + low;if (key < shuzu[mid]) {high = mid - 1;} else if (key > shuzu[mid]) {low = mid + 1;} else {return mid+1;}}return -1;}public static void main(String[] args){Scanner sc = new Scanner(System.in);Main main = new Main();while(sc.hasNext()){int n = sc.nextInt();int []shuzu = new int[n];//当时就卡在了我自己定义的数组长度这for(int i=0;i<n;i++){shuzu[i]=sc.nextInt();}int key = sc.nextInt();	System.out.println(Main.cbb(shuzu, key));}}
}