第四周习题

约定不等于承诺〃 2022-11-14 10:15 195阅读 0赞

### 习题 ###

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

# 1、字符识别 #

**题目描述**

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

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

**输入**

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

**输出**

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

**样例输入 Copy**

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

**样例输出 Copy**

123

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

## 代码 ##

#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);
                else
                   scanf("%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

## 理解 ##

这个题目我们上课就讲过啦，只要发现其中规律就不难啦~  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70_pic_center]

### 代码 ###

#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;
    	else
    		return 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 stub
    	        Scanner sc=new Scanner(System.in);
    	        Main m = new Main();
    	        while(sc.hasNext()) { 
    	        	int n=sc.nextInt();
    	            m.cbb(n);
    	        }
    		}
    }

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

### 理解 ###

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

链接：[幸运人士–Anna Qiao][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**

## 理解 ##

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

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner 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，幸好最后改对了，唉（表述不准确之处还望海涵）

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

### 代码： ###

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));
    		}
    	        
    	}
    }

[Link 1]: https://blog.csdn.net/ZCMU_2024/article/details/81634815?ops_request_misc=&request_id=&biz_id=102&utm_term=%20%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0%20%20%20%20%E4%BD%A0%E7%9A%84%E4%BB%BB%E5%8A%A1%E6%98%AF%E5%86%99%E4%B8%80%E4%B8%AA%E7%A8%8B%E5%BA%8F%E8%BF%9B%E8%A1%8C%E5%AD%97%E7%AC%A6%E8%AF%86%E5%88%AB%E3%80%82%E5%88%AB%E6%8B%85%E5%BF%83%EF%BC%8C&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-81634815.first_rank_v2_pc_rank_v29_10
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/396df57cfeef45cc8a8e7c0c93b1a529.png
[Anna Qiao]: https://blog.csdn.net/qq_46103340/article/details/115219620
[Link 2]: https://blog.csdn.net/lovesummerforever/article/details/24588989?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161692281016780255217474%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161692281016780255217474&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-24588989.first_rank_v2_pc_rank_v29_10&utm_term=%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E9%80%92%E5%BD%92