第十四周.

桃扇骨 2022-10-18 04:55 236阅读 0赞

### 回溯法 ###

*  A、菱形图案
 *   *  代码
 *  B、牛妹的蛋糕
 *   *  代码
 *  C、尼科彻斯定理
 *   *  代码
 *  D、ABC + DEF = GHI
 *   *  代码
 *  E、油田问题
 *   *  代码
 *  F、马的遍历问题
 *   *  代码

# A、菱形图案 #

**题目描述**

*  KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“\*”组成的菱形图案。

**输入**

*  多组输入，一个整数（2~20）。

**输出**

*  针对每行输入，输出用“*”组成的菱形，每个“*”后面有一个空格。每输出一个菱形的后面需要空一行。

**样例输入 Copy**

2
    3
    4

**样例输出 Copy**

* 
     * * 
    * * * 
     * * 
      * 
    
       * 
      * * 
     * * * 
    * * * * 
     * * * 
      * * 
       * 
    
        * 
       * * 
      * * * 
     * * * * 
    * * * * * 
     * * * * 
      * * * 
       * * 
        *

链接：[菱形图案][Link 1]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static void solve(int n){ 
    		for(int i=0;i<n;i++){ //上三角
    			for(int j=0;j<n-i;j++)
    				System.out.print(" ");
    			for(int k=0;k<=i;k++)
    				System.out.print("* ");
    			System.out.println();
    		}
    	}
    	public static void solve1(int n){ 
    		System.out.println();
    		for(int i=n;i>0;i--){ //下三角
    			for(int j=0;j<=n-i;j++)
    				System.out.print(" ");
    			for(int k=i;k>0;k--)
    				System.out.print("* ");
    			System.out.println();
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			solve(n);
    			int m = n;
    			while(m>=0){ 
    				System.out.print("* ");
    				m--;
    			}
    			solve1(n);
    			System.out.println();
    		}
    
    	}
    
    }

# B、牛妹的蛋糕 #

**题目描述**

*  众所周知，牛妹非常喜欢吃蛋糕。
    
    第一天牛妹吃掉蛋糕总数三分之一多一个，第二天又将剩下的蛋糕吃掉三分之一多一个，以后每天吃掉前一天剩下的三分之一多一个，到第n天准备吃的时候只剩下一个蛋糕。
    
    牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？

**输入**

*  输入n，0<n< 30。

**输出**

*  输出第一天蛋糕的数量。

**样例输入 Copy**

2
    4

**样例输出 Copy**

3
    10

链接：[牛妹的蛋糕][Link 2]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			
    			int n = sc.nextInt();
    			int cbb[] = new int[105];
    			//第一天一个蛋糕
    			cbb[1] = 1;
    			for(int i=2;i<cbb.length;i++) { 
    				//下一天的蛋糕数
    				cbb[i] = ((cbb[i-1]+1)*3)/2;
    			}
    			//输出第n天的蛋糕数
    			System.out.println(cbb[n]);
    		}
    	}
    }

# C、尼科彻斯定理 #

**题目描述**

*  验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。

例如：

1^3=1 
    
    2^3=3+5 
    
    3^3=7+9+11 
    
    4^3=13+15+17+19

**输入**

*  多组输入，输入一个整数。

**输出**

*  输出分解后的字符串。

**样例输入 Copy**

**样例输出 Copy**

31+33+35+37+39+41

链接：[戳我！戳我！][Link 3]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			if(n==1)
    				System.out.println(1);
    			int m = (int) Math.pow(n, 3);//m = n^3
    			int count = 0;
    			for(int i=1;i<(m/2);i+=2){ //最小的奇数（1除外）小于n^3的一半
    				int a = i;
    				count = i;//第一个是i,总共是n个奇数相加
    				for(int j=1;j<n;j++){ 
    					a+=2;
    					count+=a;//n个奇数和
    				}
    				if(count!=m)
    					continue;
    				else{ 
    					for(int k=0;k<n;k++){ 
    						if(k==n-1)
    							System.out.println(i+2*k);
    						else
    							System.out.print((i+2*k)+"+");
    					}
    				}
    					
    			}
    			System.out.println();
    		}
    
    	}
    
    }

# D、ABC + DEF = GHI #

**题目描述**

*  用1, 2, 3…9 这九个数字组成一个数学公式，满足：ABC + DEF = GHI，每个数字只能出现一次，编写程序输出所有的组合。

**输入**

*  无

**输出**

*  输出所有的 ABC + DEF = GHI， 每行一条数据，格式为ABC+DEF=GHI  
    输出结果按照ABC升序排列，如果ABC相同，则按照DEF升序排列。

链接： [ ABC + DEF = GHI][ABC _ DEF _ GHI]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	static int a[] = new int[15];
    	static int b[] = new int[15];
    	
    	static void solve(int n){ 
    		
    		if(n==10){ 
    			int x = a[1]*100+a[2]*10+a[3];
    			int y = a[4]*100+a[5]*10+a[6];
    			int z = a[7]*100+a[8]*10+a[9];
    			if(x+y==z)
    				System.out.println(x+"+"+y+"="+z);
    			return;
    		}
    		for(int i=1;i<10;i++){ 
    			if(b[i]==0){ 
    				a[n] = i;
    				b[i] = 1;
    				solve(n+1);
    				b[i] = 0;
    			}
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		for(int i=0;i<a.length;i++){ 
    			a[i] = 0;
    			b[i] = 0;
    		}
    		solve(1);
    
    	}
    
    }

# E、油田问题 #

**题目描述**

*  输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），即属于同一个八连块。

**输入**

*  多组输入 输入行数m，以及列数n。 然后输入\*和@ 1<=n,m<=100

**输出**

*  联通块个数

**样例输入 Copy**

5 5
    ****@
    *@@*@
    *@**@
    @@@*@
    @@**@

**样例输出 Copy**

链接：[油田问题][Link 4]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	static String str[] = new String[105];
    	static char ch[][] = new char[105][105]; 
    	static int idx[][] = new int[105][105];
    	static int m,n;
    	static int count;
    	
    	public static void solve(int x,int y,int id) { 
    		if(x<0||x>=m||y<0||y>=n)//超出数组，遍历完毕
    			return ;
    		if(idx[x][y]>0||ch[x][y]!='@')//都已经判断完成，或者没有油
    			return ;
    		idx[x][y] = id;
    		for(int dx=-1;dx<=1;dx++)//遍历八个方向
    			for(int dy=-1;dy<=1;dy++) { 
    				if(dx!=0||dy!=0)
    					solve(x+dx,y+dy,id);
    			}
    	}
    	
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		while (sc.hasNext()) { 
    			m = sc.nextInt();//行
    			n = sc.nextInt();//列
    			count = 0;
    			for (int i = 0; i < m; i++)
    				str[i] = sc.next();
    			for (int i = 0; i < m; i++)
    				for (int j = 0; j < n; j++) { 
    					idx[i][j] = 0;
    					ch[i] = str[i].toCharArray();//获取字符
    				}
    			
    			for (int i = 0; i < m; i++)
    				for (int j = 0; j < n; j++) { 
    					if(idx[i][j]==0&&ch[i][j]=='@')//没有搜过并且有油
    						solve(i,j,++count);//遍历其他八个方向
    				}
    			System.out.println(count);
    		}
    	}
    }

# F、马的遍历问题 #

**题目描述**

*  在5\*4的棋盘中，马只能走斜“日”字。马从位置(x, y)处出发，把棋盘的每一格都走一次，且只走一次，请找出所有路径。

**输入**

*  x,y，表示马的初始位置。

**输出**

*  将每一格都走一次的路径总数，如果不存在该路径则输出“No solution!”。

**样例输入 Copy**

1 1
    2 2

**样例输出 Copy**

32
    No solution!

链接：[马的遍历问题][Link 5]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	static int over[][] = new int[105][105];//这个位置是否走过
    	static int count;//记录有几条路径
    	
    	public static void solve(int x,int y,int step){ 
    		if(step==20){ 
    			count++;
    			return;
    		}
    		//方向引导数组
    		int dx[] = { 1,2, 2, 1,-1,-2,-2,-1};
    		int dy[] = { 2,1,-1,-2,-2,-1, 1, 2};
    		int DX,DY;
    		for(int i=0;i<=7;i++){ 
    			DX = x+dx[i];
    			DY = y+dy[i];
    			if(cut(DX,DY)){ 
    				over[x][y] = step;
    				solve(DX,DY,step+1);
    				over[x][y] = 0;
    			}
    		}
    	}
    	
    	//剪枝函数
    	public static boolean cut(int x,int y){ 
    		//超出棋盘的位置或者被走过的位置
    		if(x>=1 && x<=5 && y>=1 && y<=4 && over[x][y]==0)
    			return true;
    		else
    			return false;
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int x = sc.nextInt();
    			int y = sc.nextInt();
    			
    			for(int i=1;i<5;i++)
    				for(int j=1;j<5;j++)
    					over[i][j] = 0;
    			count = 0;
    			solve(x,y,1);
    			if(count==0)
    				System.out.println("No solution!");
    			else
    				System.out.println(count);
    		}
    
    	}
    
    }

> 【下周开始考试了，要赶快准备英语口语课毛概了，六级感觉可能过不了了，哭唧唧~啊，好难啊，还要搞课设】  
> 句子君：
> 
> > “曾经发生过的事情不可能忘记，只不过是想不起而已。  
> > –宫崎骏 《千与千寻》”

[Link 1]: https://blog.csdn.net/qq_46546793/article/details/106012411
[Link 2]: https://blog.csdn.net/qq_46546793/article/details/106082918
[Link 3]: https://blog.csdn.net/qq_46546793/article/details/106091569
[ABC _ DEF _ GHI]: https://blog.csdn.net/Y_yunhu/article/details/96475274
[Link 4]: https://blog.csdn.net/qq_46546793/article/details/106134482
[Link 5]: https://blog.csdn.net/qq_46546793/article/details/106254639