几个有意思的算法题

向右看齐 2022-09-18 03:56 168阅读 0赞

### 1.题目标题: 高斯日记 ###

大数学家高斯有个好习惯：无论如何都要记日记。

他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210

后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？

高斯出生于：1777年4月30日。  
     
    在高斯发现的一个重要定理的日记上标注着：5343，因此可算出那天是：1791年12月15日。

高斯获得博士学位的那天日记上标着：8113

请你算出高斯获得博士学位的年月日。

提交答案的格式是：yyyy-mm-dd, 例如：1980-03-21

请严格按照格式，通过浏览器提交答案。  
注意：只提交这个日期，不要写其它附加内容，比如：说明性的文字。

分析：这实际就是“三天打鱼、两天晒网问题”。

程序实现：（java写的）

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  package Forth;  
2.    
3.  public class DateOfNdays \{  
4.  /\* 
5.   \* 高斯日记(给定日期，算出X天后的日期) 
6.   \*/  
7.      /\* 
8.       \* 是否是闰年 
9.       \*/  
10.     boolean IsleapYear(int year)\{  
11.         return (year % 400 == 0 || year % 4 == 0 && year != 100);  
12.     \}  
13.       
14.     /\* 
15.      \* 获得某年某月的最大天数 
16.      \*/  
17.     int GetMaxDay(int year,int month,int day)\{  
18.         switch(month)\{  
19.         case 1:  
20.         case 3:  
21.         case 5:  
22.         case 7:  
23.         case 8:  
24.         case 10:  
25.         case 12:  
26.             return 31;  
27.         case 4:  
28.         case 6:  
29.         case 9:  
30.         case 11:  
31.             return 30;  
32.         case 2:  
33.             return (IsleapYear(year)?29:28);  
34.         default:  
35.             return -1;  
36.         \}  
37.     \}  
38.     /\* 
39.      \* 获得X天后的日期 
40.      \*/  
41.     void GetXDays(int year,int month,int day,int X)\{  
42.         for(int i = 1; i <= X; i++)\{  
43.             if(day != GetMaxDay(year,month,day))\{  
44.                 day++;  
45.             \}else\{  
46.                 if(month != 12)\{  
47.                     month++;  
48.                     day = 1;  
49.                 \}else\{  
50.                     month = day = 1;  
51.                     year++;  
52.                 \}  
53.             \}  
54.                   
55.         \}  
56.         System.out.println(X+"天后的日期是"\+year+"/"\+month+"/"\+day);  
57.     \}  
58.   
59. \}

package Forth;
    
    public class DateOfNdays {
    /*
     * 高斯日记(给定日期，算出X天后的日期)
     */
    	/*
    	 * 是否是闰年
    	 */
    	boolean IsleapYear(int year){
    		return (year % 400 == 0 || year % 4 == 0 && year != 100);
    	}
    	
    	/*
    	 * 获得某年某月的最大天数
    	 */
    	int GetMaxDay(int year,int month,int day){
    		switch(month){
    		case 1:
    		case 3:
    		case 5:
    		case 7:
    		case 8:
    		case 10:
    		case 12:
    			return 31;
    		case 4:
    		case 6:
    		case 9:
    		case 11:
    			return 30;
    		case 2:
    			return (IsleapYear(year)?29:28);
    		default:
    			return -1;
    		}
    	}
    	/*
    	 * 获得X天后的日期
    	 */
    	void GetXDays(int year,int month,int day,int X){
    		for(int i = 1; i <= X; i++){
    			if(day != GetMaxDay(year,month,day)){
    				day++;
    			}else{
    				if(month != 12){
    					month++;
    					day = 1;
    				}else{
    					month = day = 1;
    					year++;
    				}
    			}
    				
    		}
    		System.out.println(X+"天后的日期是"+year+"/"+month+"/"+day);
    	}
    
    }

答案：1799-7-16

### 2.题目标题: 排它平方数 ###

小明正看着 203879 这个数字发呆。

原来，203879 \* 203879 = 41566646641

这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。

具有这样特点的6位数还有一个，请你找出它！

再归纳一下筛选要求：  
    1. 6位正整数  
    2. 每个数位上的数字不同  
    3. 其平方数的每个数位不含原数字的任何组成数位

答案是一个6位的正整数。

请通过浏览器提交答案。  
注意：只提交另一6位数，题中已经给出的这个不要提交。  
注意：不要书写其它的内容（比如：说明性的文字）。

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  package Forth;  
2.    
3.  public class ExcludeNumber \{  
4.  /\* 
5.   \* 排它平方数 
6.   \*/  
7.      long PingNum = 0; //存储平方  
8.        
9.      /\* 
10.      \* 判断一个数是否有重复数字 
11.      \*/  
12.     public boolean IsSame(long x)\{  
13.         long store\[\] = new long\[7\];  
14.         long r;  
15.         int i = 0;  
16.         while(x != 0)\{ //分离该数的每一位，存入store数组  
17.             r = x % 10;  
18.             x = x / 10;  
19.             store\[i\] = r;  
20.             i++;  
21.         \}  
22.           
23.         long result;  
24.         for(int j = 0; j < 5; j++)\{ //判断有无重复数  
25.             result = store\[j\];  
26.             for(int k = j+1; k < 6; k++)\{  
27.                 if(result == store\[k\])  
28.                     return true;  
29.             \}  
30.         \}  
31.           
32.         return false;  
33.     \}  
34.     public boolean IsSame2(long Num,long n)\{  
35.         long store\[\] = new long\[7\];  
36.         long r;  
37.         int i = 0;  
38.         while( n != 0)\{  
39.             r = n % 10;  
40.             n = n / 10;  
41.             store\[i\] = r;  
42.             i++;  
43.         \}  
44.           
45.         long storeping\[\] = new long\[18\];  
46.         i = 0;  
47.         while(Num != 0)\{  
48.             r = Num % 10;  
49.             Num = Num / 10;  
50.             storeping\[i\] = r;  
51.             i++;  
52.         \}  
53.                   
54.         for(int k = 0; k < 6; k++)\{   //将该数的每一位与其平方的每一位比较，看是否有相同的数  
55.             for(int j = 0; j < i; j++)\{  
56.                 if(store\[k\] == storeping\[j\])  
57.                     return true;  
58.             \}  
59.         \}  
60.           
61.         return false;  
62.     \}  
63.       
64.     public void selectNum()\{ //筛选排他数  
65.           
66.         for(long n = 100000; n <= 999999;n++)\{  
67.             if(IsSame(n))  //有相同的数字，则跳过  
68.                 continue;  
69.             else\{  
70.                 PingNum = n\*n;  
71.                 if(IsSame2(PingNum,n)) //该数的平方中是否有与该数相同的数字  
72.                     continue;  
73.                 else                   //符合条件，则打印  
74.                     System.out.println(n);  
75.             \}  
76.         \}  
77.     \}  
78. \}

package Forth;
    
    public class ExcludeNumber {
    /*
     * 排它平方数
     */
    	long PingNum = 0; //存储平方
    	
    	/*
    	 * 判断一个数是否有重复数字
    	 */
    	public boolean IsSame(long x){
    		long store[] = new long[7];
    		long r;
    		int i = 0;
    		while(x != 0){ //分离该数的每一位，存入store数组
    			r = x % 10;
    			x = x / 10;
    			store[i] = r;
    			i++;
    		}
    		
    		long result;
    		for(int j = 0; j < 5; j++){ //判断有无重复数
    			result = store[j];
    			for(int k = j+1; k < 6; k++){
    				if(result == store[k])
    					return true;
    			}
    		}
    		
    		return false;
    	}
    	public boolean IsSame2(long Num,long n){
    		long store[] = new long[7];
    		long r;
    		int i = 0;
    		while( n != 0){
    			r = n % 10;
    			n = n / 10;
    			store[i] = r;
    			i++;
    		}
    		
    		long storeping[] = new long[18];
    		i = 0;
    		while(Num != 0){
    			r = Num % 10;
    			Num = Num / 10;
    			storeping[i] = r;
    			i++;
    		}
    				
    		for(int k = 0; k < 6; k++){   //将该数的每一位与其平方的每一位比较，看是否有相同的数
    			for(int j = 0; j < i; j++){
    				if(store[k] == storeping[j])
    					return true;
    			}
    		}
    		
    		return false;
    	}
    	
    	public void selectNum(){ //筛选排他数
    		
    		for(long n = 100000; n <= 999999;n++){
    			if(IsSame(n))  //有相同的数字，则跳过
    				continue;
    			else{
    				PingNum = n*n;
    				if(IsSame2(PingNum,n)) //该数的平方中是否有与该数相同的数字
    					continue;
    				else                   //符合条件，则打印
    					System.out.println(n);
    			}
    		}
    	}
    }

答案：639172

### 3.标题: 振兴中华 ###

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。

地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）

从我做起振  
我做起振兴  
做起振兴中  
起振兴中华

比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

要求跳过的路线刚好构成“从我做起振兴中华”这句话。

请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

答案是一个整数，请通过浏览器直接提交该数字。  
注意：不要提交解答过程，或其它辅助说明类的内容。

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  /\* 
2.   \* 振兴中华 
3.   \*/  
4.      int array\[\]\[\] =   
5.             \{ \{ 0,1,2,3,4\},  
6.              \{ 1,2,3,4,5\},  
7.              \{ 2,3,4,5,6\},  
8.              \{ 3,4,5,6,7\}\};  
9.      int copyarray\[\]\[\] = new int\[4\]\[5\]; //显示路径的拷贝数组  
10.     int startI = 0, startJ = 0;  // 入口  
11.     int endI = 3, endJ = 4;  // 出口  
12.     int success = 0;  
13.     int count = 0;  
14.   
15.       
16.     /\* 
17.      \* 初始化拷贝数组 
18.      \*/  
19.     public void initcopy()\{   
20.         for(int k = 0; k < 4; k++)\{  
21.             for(int d = 0; d < 5; d++)\{  
22.                 copyarray\[k\]\[d\] = 10;  
23.             \}  
24.         \}  
25.     \}  
26.     /\* 
27.      \* 遍历访问 
28.      \*/  
29.     public void visit(int i,int j)\{  
30.             copyarray\[i\]\[j\] = array\[i\]\[j\];  
31.         if(i == endI &&  j == endJ)\{  
32.             count++;  
33.             System.out.print("\\n 显示路径：\\n");  
34.             for(int k = 0; k < 4; k++)\{  
35.                 for(int d = 0; d < 5; d++)\{  
36.                     if(copyarray\[k\]\[d\] == 0)  
37.                         System.out.print("从");  
38.                     else if(copyarray\[k\]\[d\] == 1)  
39.                         System.out.print("我");  
40.                     else if(copyarray\[k\]\[d\] == 2)  
41.                         System.out.print("做");  
42.                     else if(copyarray\[k\]\[d\] == 3)  
43.                         System.out.print("起");  
44.                     else if(copyarray\[k\]\[d\] == 4)  
45.                         System.out.print("振");  
46.                     else if(copyarray\[k\]\[d\] == 5)  
47.                         System.out.print("兴");  
48.                     else if(copyarray\[k\]\[d\] == 6)  
49.                         System.out.print("中");  
50.                     else if(copyarray\[k\]\[d\] == 7)  
51.                         System.out.print("华");    
52.                     else if(copyarray\[k\]\[d\] == 10)  
53.                         System.out.print("一");    
54.                     else   
55.                         System.out.print("一");    
56.   
57.                 \}  
58.                 System.out.println();  
59.             \}  
60.         \}  
61.         if(j != 4 && array\[i\]\[j+1\] == array\[i\]\[j\]+1) visit(i,j+1);  
62.         if(i != 3 && array\[i+1\]\[j\] == array\[i\]\[j\]+1) visit(i+1,j);  
63.           
64.         copyarray\[i\]\[j\] = 10;  
65.     \}  
66.     /\* 
67.      \* 主调方法 
68.      \*/  
69.     public void test()\{  
70.   
71.         initcopy();  
72.         visit(startI,startJ);  
73.         System.out.println("共有 "\+count+" 种");  
74.     \}  
75.       
76. \}

/*
     * 振兴中华
     */
    	int array[][] = 
    		   {
       {0,1,2,3,4},
    			{1,2,3,4,5},
    			{2,3,4,5,6},
    			{3,4,5,6,7}};
    	int copyarray[][] = new int[4][5]; //显示路径的拷贝数组
    	int startI = 0, startJ = 0;  // 入口
    	int endI = 3, endJ = 4;  // 出口
    	int success = 0;
    	int count = 0;
    
    	
    	/*
    	 * 初始化拷贝数组
    	 */
    	public void initcopy(){ 
    		for(int k = 0; k < 4; k++){
    			for(int d = 0; d < 5; d++){
    				copyarray[k][d] = 10;
    			}
    		}
    	}
    	/*
    	 * 遍历访问
    	 */
    	public void visit(int i,int j){
    			copyarray[i][j] = array[i][j];
    		if(i == endI &&  j == endJ){
    			count++;
    			System.out.print("\n 显示路径：\n");
    			for(int k = 0; k < 4; k++){
    				for(int d = 0; d < 5; d++){
    					if(copyarray[k][d] == 0)
    						System.out.print("从");
    					else if(copyarray[k][d] == 1)
    						System.out.print("我");
    					else if(copyarray[k][d] == 2)
    						System.out.print("做");
    					else if(copyarray[k][d] == 3)
    						System.out.print("起");
    					else if(copyarray[k][d] == 4)
    						System.out.print("振");
    					else if(copyarray[k][d] == 5)
    						System.out.print("兴");
    					else if(copyarray[k][d] == 6)
    						System.out.print("中");
    					else if(copyarray[k][d] == 7)
    						System.out.print("华");	
    					else if(copyarray[k][d] == 10)
    						System.out.print("一");	
    	                else 
    	                	System.out.print("一");	
    
    				}
    				System.out.println();
    			}
    		}
    		if(j != 4 && array[i][j+1] == array[i][j]+1) visit(i,j+1);
    		if(i != 3 && array[i+1][j] == array[i][j]+1) visit(i+1,j);
    		
    		copyarray[i][j] = 10;
    	}
    	/*
    	 * 主调方法
    	 */
    	public void test(){
    
    		initcopy();
    		visit(startI,startJ);
    		System.out.println("共有 "+count+" 种");
    	}
    	
    }

结果截图:

![SouthEast][]

### 4.标题: 颠倒的价牌 ###

小李的店里专卖其它店中下架的样品电视机，可称为：样品电视专卖店。

其标价都是4位数字（即千元不等）。

小李为了标价清晰、方便，使用了预制的类似数码管的标价签，只要用颜色笔涂数字就可以了（参见p1.jpg）。

这种价牌有个特点，对一些数字，倒过来看也是合理的数字。如：1 2 5 6 8 9 0 都可以。这样一来，如果牌子挂倒了，有可能完全变成了另一个价格，比如：1958 倒着挂就是：8561，差了几千元啊!!

当然，多数情况不能倒读，比如，1110 就不能倒过来，因为0不能作为开始数字。

有一天，悲剧终于发生了。某个店员不小心把店里的某两个价格牌给挂倒了。并且这两个价格牌的电视机都卖出去了!

庆幸的是价格出入不大，其中一个价牌赔了2百多，另一个价牌却赚了8百多，综合起来，反而多赚了558元。

请根据这些信息计算：赔钱的那个价牌正确的价格应该是多少？

答案是一个4位的整数，请通过浏览器直接提交该数字。  
注意：不要提交解答过程，或其它辅助说明类的内容。

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  package Forth;  
2.    
3.  public class ReverseNumber \{  
4.    
5.      /\* 
6.       \* 实现数字的翻转 
7.       \*/  
8.      public int reverse(int n)\{  
9.        
10.         int store\[\] = new int\[4\];  
11.         int result = 0;  
12.         int r;  
13.         int i = 0;  
14.           
15.         while( n != 0)\{ //分离每个数，存入store中  
16.             r = n % 10;  
17.             n = n / 10;  
18.             store\[i\] = r;  
19.             i++;  
20.         \}  
21.         for(int k = 0; k < i; k++)\{  
22.             if(store\[k\] == 3 || store\[k\] == 4 || store\[k\] == 7)//数字中有3、4、7的不能翻转  
23.                 return -1;  
24.             else if(store\[k\] == 6)//数字中有6,则转为9  
25.                 store\[k\] = 9;  
26.             else if(store\[k\] == 9)//数字中有9,则转为6  
27.                 store\[k\] = 6;  
28.         \}  
29.         for(int j = 0; j < i; j++)\{ //计算翻转后的数  
30.             if(store\[0\] == 0) //最后一个数字为0,不能翻转  
31.                 return -1;  
32.               
33.             if(j == 0)  
34.                 result = store\[j\];  
35.             else  
36.                 result = result\*10 +store\[j\];  
37.         \}  
38.   
39.     //  System.out.println(result);  
40.         return result;  
41.     \}  
42.     public void selectNum()\{  
43.         int sub = 0;  
44.         int sub2 = 0;  
45.       
46.         for(int i = 1000; i <= 9999; i++)\{ //遍历所有4位数  
47.               
48.             if(reverse(i) == -1)  
49.                 continue;  
50.             sub = i-reverse(i);  
51.               
52.             if(sub < 200 || sub >= 300)  
53.                 continue;  
54.             for(int j = 1000; j <= 9999; j++)\{  
55.                   
56.                 if(reverse(j) == -1)  
57.                     continue;  
58.                 sub2 = reverse(j)-j;  
59.                   
60.                 if(sub2 < 800 || sub2 >= 900)  
61.                     continue;     
62.                 if((sub2-sub) == 558)\{  
63.                     System.out.println("赔钱的正确价格为："\+i);  
64.                     //System.out.println("赚钱的正确价格为："+j);  
65.                 \}  
66.             \}  
67.         \}  
68.           
69.     \}  
70. \}

package Forth;
    
    public class ReverseNumber {
    
    	/*
    	 * 实现数字的翻转
    	 */
    	public int reverse(int n){
    	
    		int store[] = new int[4];
    		int result = 0;
    		int r;
    		int i = 0;
    		
    		while( n != 0){ //分离每个数，存入store中
    			r = n % 10;
    			n = n / 10;
    			store[i] = r;
    			i++;
    		}
    		for(int k = 0; k < i; k++){
    			if(store[k] == 3 || store[k] == 4 || store[k] == 7)//数字中有3、4、7的不能翻转
    				return -1;
    			else if(store[k] == 6)//数字中有6,则转为9
    				store[k] = 9;
    			else if(store[k] == 9)//数字中有9,则转为6
    				store[k] = 6;
    		}
    		for(int j = 0; j < i; j++){//计算翻转后的数
    			if(store[0] == 0) //最后一个数字为0,不能翻转
    				return -1;
    			
    			if(j == 0)
    				result = store[j];
    			else
    			    result = result*10 +store[j];
    		}
    
    	//	System.out.println(result);
    		return result;
    	}
    	public void selectNum(){
    		int sub = 0;
    		int sub2 = 0;
    	
    		for(int i = 1000; i <= 9999; i++){//遍历所有4位数
    			
    		    if(reverse(i) == -1)
    		    	continue;
    		    sub = i-reverse(i);
    		    
    		    if(sub < 200 || sub >= 300)
    		    	continue;
    			for(int j = 1000; j <= 9999; j++){
    				
    				if(reverse(j) == -1)
    					continue;
    				sub2 = reverse(j)-j;
    				
    				if(sub2 < 800 || sub2 >= 900)
    					continue;	
    				if((sub2-sub) == 558){
    					System.out.println("赔钱的正确价格为："+i);
    					//System.out.println("赚钱的正确价格为："+j);
    				}
    			}
    		}
    		
    	}
    }

答案：9088

[view plain]: http://blog.csdn.net/u012027907/article/details/14157077#
[SouthEast]: /images/20220828/b64463587a724ebbab69d4c5196bd8db.png