一个小学弟问我的算法问题

  在实验室的本科群中，一个小弟问我一个算法问题。说有1,2,3,4,5构成的6位数，其中第3位不能为4，3和5不能连着，请把所有情况结果找出来。由于大四了，要做课程设计，由于在专业实验室里面没有eclipse，所以只好用C语言编写了（java的也差不多，所以都看得懂），没用多久时间，就是感觉时间效率不是很好。哪位大侠指点指点。

#include<stdio.h>
void main(){
	int i,j,k,l,m,n;
	int a,b,c,d,e,f;
	for(i=1;i<=5;i++){
		a=i;
		for(j=1;j<=5;j++){
			if((a==3&&j==5)||(a==5&&j==3)){
				continue;
			}
			b=j;
			for(k=1;k<=5;k++){
			   if((b==3&&k==5)||(b==5&&k==3)||k==4){
				continue;
			   }
		 	   c=k;
			   for(l=1;l<=5;l++){
				   if((c==3&&l==5)||(c==5&&l==3)){
				   continue;
				   }
		 	       d=l;
				   for(m=1;m<=5;m++){
					  if((d==3&&m==5)||(d==5&&m==3)){
				      continue;
					   }
		 	           e=m;
					   for(n=1;n<=5;n++){
						   if((e==3&&n==5)||(e==5&&n==3)){
				            continue;
						   }
		 	               f=n;
						   printf("%d%d%d%d%d%d\r\n",a,b,c,d,e,f);
					   }
				   }
			   }
			}
		}
	}
}

评论

5 楼 raojl 2011-09-05  

这不是卖彩票嘛？

4 楼 zengzhaoshuai 2011-09-05  

* @author:     Hongze Zhao 
你的这个深度搜索很犀利，受教了，谢谢了

3 楼 randyzhao 2011-09-05  

刚才代码有个字写错了。

/**  
* Filename:    Number.java  
* Description:   
* Copyright:   Copyright (c)2011 
* Company:    company 
* @author:     Hongze Zhao 
* @version:    1.0  
* Create at:   Sep 5, 2011 1:28:01 AM  
*  
* Modification History:  
* Date         Author      Version     Description  
* ------------------------------------------------------------------  
* Sep 5, 2011    Hongze Zhao   1.0         1.0 Version  
*/
package testpackge;

/**Description:
 * @author Hongze Zhao
 * Create At : Sep 5, 2011 1:28:01 AM
 */
public class Number {
	private int[] num;//current number
	private int length;//the length of the number
	/**
	 * Use dfs to solve the problem
	 * @param pace current pacce
	 * @author Hongze Zhao	
	 */
	private void dfs(int pace){
		if (pace == this.length){
			//end, output
			for (int i = 0; i < this.length; i++){
				System.out.print(this.num[i]);
				
			}
			System.out.print("\n");
			return;
		}
		
		for (int i = 1; i <= 5; i++){
			if (pace == 2 && i == 4) {
				continue;
			}
			
			if (pace != 0 && i * this.num[pace - 1] == 15){
				continue;
			}
			
			this.num[pace] = i;
			this.dfs(pace + 1);
		}
	}
	public Number(int length){
		this.length = length;
		this.num = new int[length];
		this.dfs(0);
	}
	public static void main(String[] args){
		new Number(6);
	}
}

2 楼 randyzhao 2011-09-05  

Lz的代码怎么这么丑陋。用一个深搜就可以了。

/**  
* Filename:    Number.java  
* Description:   
* Copyright:   Copyright (c)2011 
* Company:    company 
* @author:     Hongze Zhao 
* @version:    1.0  
* Create at:   Sep 5, 2011 1:28:01 AM  
*  
* Modification History:  
* Date         Author      Version     Description  
* ------------------------------------------------------------------  
* Sep 5, 2011    Hongze Zhao   1.0         1.0 Version  
*/
package testpackge;

/**Description:
 * @author Hongze Zhao
 * Create At : Sep 5, 2011 1:28:01 AM
 */
public class Number {
	private int[] num;//current number
	private int length;//the length of the number
	/**
	 * Use dfs to solve the problem
	 * @param pace current pacce
	 * @author Hongze Zhao	
	 */
	private void dfs(int pace){
		if (pace == this.length){
			//end, output
			for (int i = 0; i < this.length; i++){
				System.out.print(this.num[i]);
				
			}
			System.out.print("\n");
			return;
		}
		
		for (int i = 1; i <= 5; i++){
			if (pace == 2 && i == 4) {
				continue;
			}
			
			if (pace != 0 && this.num[pace] * this.num[pace - 1] == 15){
				continue;
			}
			
			this.num[pace] = i;
			this.dfs(pace + 1);
		}
	}
	public Number(int length){
		this.length = length;
		this.num = new int[length];
		this.dfs(0);
	}
	public static void main(String[] args){
		new Number(6);
	}
}

1 楼 putersham 2011-09-04  

先不考虑3跟5连在一起的情况

那么应该有
5*5*4*5*5*5=12500
种情况

全部生产出来存入数组
应该这个量也不算很过分吧，才12500个值

如果超过6位的话那么就需要用数据库了
如果是超过10位的话已经几千万了 那么数据库估计也不好用了就 呵呵

接下来遍历数组，检查有没有35 或者53，有就从数组里移除

最后剩下的就是你要的了哦