2021-3-21-第三周

妖狐艹你老母 2021-09-07 06:19 386阅读 0赞

### 习题 ###

*  A、超级青蛙
 *   *  代码
 *  B、汉诺塔
 *   *  代码
 *  C、汉诺塔||
 *   *  代码
 *  D、Kimi的早餐店
 *   *  代码
 *  E、字母全排列
 *   *  代码
 *  F、九组数分数
 *   *  代码

# A、超级青蛙 #

**题目描述**

*  一只超级青蛙一次可以跳上1级台阶，也可以跳上2级……它也能够跳上n级台阶。请问，该青蛙跳上一个n级的台阶总共有多少种跳法？

**输入**

*  输入一个正整数n表示台阶的数量。

**输出**

*  输出总的跳法数。

**样例输入 Copy**

1
    2

**样例输出 Copy**

1
    2

## 代码 ##

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 n;
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			int he=1;
    			for(int i=1;i<n;i++){ 
    				he*=2;
    			}
    			System.out.println(he);
    		}
    
    	}
    
    }

*  【这个其实找规律的话，就比较好理解啦 ，因为我们老师上课的时候讲啦，所以这个我依旧找了CSDN的文章看了看，因为自己写的还是有些错误！不过大家也可以看那一下这篇文章欧~[青蛙跳哒哒哒][Link 1]  
    点击蓝色字体就好啦~】

# B、汉诺塔 #

**题目描述**

*  使用递归编写一个程序实现汉诺塔问题，要求在输入圆盘数量之后，输出圆盘的移动步骤，输出格式示例如下：

第1步：1号盘从A柱移至B柱 
    第2步：2号盘从A柱移至C柱

**输入**

*  多组测试用例，每组输入一个正整数n，n代表圆盘数量。

**输出**

*  每组输出之间有一行空行。

**样例输入 Copy**

**样例输出 Copy**

第1步:1号盘从A柱移至C柱
    第2步:2号盘从A柱移至B柱
    第3步:1号盘从C柱移至B柱
    第4步:3号盘从A柱移至C柱
    第5步:1号盘从B柱移至A柱
    第6步:2号盘从B柱移至C柱
    第7步:1号盘从A柱移至C柱

## 代码 ##

#include<stdio.h>
    int i=0;
    void cbb(int n,char x,char y){ 
    	printf("第%d步:%d号盘从%c柱移至%c柱\n",++i,n,x,y);//1号盘从A柱移至B柱
    }
    void move(int n, char x, char y, char z)//将n个圆盘从x柱子上借助y柱子移动到z柱子上
    { 
         if(n>0)
         { 
             move(n-1,x,z,y);
             cbb(n,x,z);
             move(n-1,y,x,z);
          }
     }
    int main()
    { 
    	
        int n;//n代表圆盘的个数
        /*A,B,C分别代表三个柱子*/
        /*char ch1 ='A'; char ch2 = 'B'; char ch3 = 'C';*/
         
        while(scanf("%d",&n)!=EOF){ 
    		i=0;
    		move(n,'A','B','C');
    		printf("\n");
    	}
         return 0;
    }

*  【一定要注意看题目要求，看是英文符号还是中文符号，看是否需要换行，然后的话，CSDN还是有很多大佬的文章的，然后有些大佬的讲解十分厉害，大家找到了一定要看懂哦，也可以分享给同学们呀！(๑•̀ㅂ•́)و✧】

# C、汉诺塔|| #

**题目描述**

*  用1,2,…,n表示n个盘子，称为1号盘，2号盘,…。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘子总数和盘号，计算该盘子的移动次数.

**输入**

*  包含多组数据，首先输入T,表示有T组数据.每个数据一行，是盘子的数目N(1<=N<=60)和盘号k(1<=k<=N)。

**输出**

*  对于每组数据，输出一个数，到达目标时k号盘需要的最少移动数。

**样例输入 Copy**

2
    60 1
    3 1

**样例输出 Copy**

576460752303423488
    4

## 代码 ##

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

*  【这就是升级版啦，我给你们找个链接：[汉诺塔][Link 2]  
    这个好像还行，不过是第一个汉诺塔的[兄弟们，我尽力了，我真的找不到那个让我修改正确的文章了，这个文章也可以看看，对于那个原作，真的很抱歉啊][Link 3]】

# D、Kimi的早餐店 #

**题目描述**

*  Kimi开了一家早餐店，这家店的客人都有个奇怪的癖好：他们只要来这家店吃过一次早餐，就会每天都过来；并且，所有人在这家店吃了两天早餐后，接下来每天都会带一位新朋友一起来品尝。
    
    于是，这家店的客人从最初一个人发展成浩浩荡荡成百上千人：1、1、2、3、5……  
    现在，Kimi想请你帮忙统计一下，某一段时间范围那他总共卖出多少份早餐（假设每位客人只吃一份早餐）。

**输入**

*  测试数据包括多组。 每组数据包含两个整数from和to(1≤from≤to≤80)，分别代表开店的第from天和第to天。

**输出**

*  对应每一组输入，输出从from到to这些天里（包含from和to两天），需要做多少份早餐。

**样例输入 Copy**

1 2
    1 3
    2 3

**样例输出 Copy**

2
    4
    3

## 代码 ##

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class Main { 
    	public static Map<Integer,Long>map = new HashMap<Integer,Long>();
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		int from,to,i;
    		while(sc.hasNext()) { 
    			from = sc.nextInt();
    			to = sc.nextInt();
    			long juele = 0;
    			String [] cbb = new String[80];
    			for(i=from;i<=to;i++) { 
    				juele+=cdbb(i);
    			}
    			System.out.println(juele);
     
    		}
    
    	}
    	public static long cdbb(int n) { 		
    		if(n==1)
    			return 1;
    		else if(n==2)
    			return 1;
    		else { 
    			if(map.containsKey(n)) 
    				return map.get(n);			
    			else
    				map.put(n, cdbb(n-1)+cdbb(n-2));
    		}
    		return map.get(n);		
    	}
    
    }

*  【兄弟们，你们理解，我知道有斐波那契数列，并且我是用了递归，结果超限了的悲哀吗？哭唧唧啊~QAQ难过，只能用数组，对不起原作】

# E、字母全排列 #

**题目描述**

*  编写一个程序，使用递归算法输出一个一维字符数组中所有字符的全排列，假设字符都不一样。例如\{‘a’,‘b’,‘c’\}的全排列为(a,b,c),(a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)

**输入**

*  多组测试用例，每组输入一个正整数n(0<n<=26)。

**输出**

*  输出从a开始，连续n个字母的全排列，且每组输出之间用**空格**隔开。

**样例输入 Copy**

1
    2

**样例输出 Copy**

a
    
    ab
    ba

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static void cbb(char[] cdbb,int first,int second) { 
    		char temp;
    		if(first==second) { 
    			//当只要求对数组中一个字母进行全排列时，只要按该数组输出即可
    			for(int i=0;i<=second;i++)
    				System.out.print(cdbb[i]);
    			System.out.println(" ");
    		}
    		else { //多个字母全排列
    			for(int i=first;i<=second;i++) { 
    				temp = cdbb[first];//交换数组第一个元素与后续的元素
    				cdbb[first] = cdbb[i];
    				cdbb[i] = temp;
    				cbb(cdbb,first+1,second);//后续元素递归全排列
    				temp = cdbb[i];
    				cdbb[i] = cdbb[first];
    				cdbb[first] = temp;//将交换后的数组还原
    			}
    			
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		int n;
    		while(sc.hasNext()) { 
    			n = sc.nextInt();
    			if(0<n&&n<=26){ 
    			char[] ch = new char[] { 'a','b','c','d','e','f','g','h','i','j','k','l',
    					'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};		
    			cbb(ch,0,n-1);
    			}
    		}
    
    	}
    	
    
    }

> 【不要学我广大朋友们，我只是懒，且不会，不至于把26个字母全写上，可以用其他方法，不知道问什么平台给我过了】

# F、九组数分数 #

**题目描述**

*  1, 2, 3…9 这九个数字组成一个分数，其值恰好为1/3，要求每个数字出现且只能出现一次，如何组合？编写程序输出所有的组合。

**输入**

*  无

**输出**

*  输出所有的结果，如果有多个，每条结果占一行。 结果的格式 : xxxx/xxxxx ，按照分子从小到大的顺序输出。

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void cbb(int[] cdbb) { 
    		
    		int a = cdbb[0]*1000+cdbb[1]*100+cdbb[2]*10+cdbb[3];//分子
    		
    		//分母
    		int b = cdbb[4]*10000+cdbb[5]*1000+cdbb[6]*100+cdbb[7]*10+cdbb[8];
    	
    		if(a*3==b) { 
    			System.out.println(a+"/"+b);
    		}
    	}
    	
    	public static void first(int bb[],int k,int n) { // 全排列
    		int i,temp;
    		if(k==n) { 
    			cbb(bb);
    		}
    		for(i=n;i>=k;i--) { 
    			
    			{ temp =  bb[k];//交换数组第一个元素与后续的元素
    			 bb[k] =  bb[i];
    			 bb[i] = temp;}
    			
    			first( bb,k+1,n);//后续元素递归全排列
    			
    			{ temp =  bb[i];
    			 bb[i] =  bb[k];
    			 bb[k] = temp;//将交换后的数组还原
    			 }
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		int n;
    		
    		int fan[] = new int[]{ 1,2,3,4,5,6,7,8,9};
    		
    		n = fan.length;
    		
    		first(fan,0,n-1);
    
    	}
    
    }

*  【做这些题目的时候也搜了很多大神们的代码，然后修修改改，于此哦，我只是简单记录一下，忘记搜了那些文章了，所以也没办法复制链接】

[Link 1]: https://blog.csdn.net/qq_45955439/article/details/115032855
[Link 2]: https://blog.csdn.net/acm_yuuji/article/details/19976437
[Link 3]: https://blog.csdn.net/wj1098286097/article/details/83444890