findthemultiple.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 52 行

package PKU.DFS;
import java.util.Scanner;


/**
 * ID:1426
 * DFS
 * @author yhm
 *
 */
public class FindTheMultiple {

	static int n;
	static int[] a = new int[101];
	static int ac;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			n = cin.nextInt();
			if(n==0){
				break;
			}
			a[0] = 1;
			ac = 0;
			dfs(1,1);
		}

	}
	

	static void dfs(int c, int s)
	{
	        if(s==0&&ac==0)
	        {//得到结果，直接输出
	                for(int i=0;i<c;i++) System.out.print(a[i]);
	                System.out.println();
	                ac = 1;//修改状态为已得到结果
	        }
	        else if(c < 100&&ac==0)//未得到结果且深度为100以下的前提下进行递归
	        {
	                a[c] = 1;
	                dfs(c + 1, (s * 10 + 1) % n);
	                a[c] = 0;
	                dfs(c + 1, (s * 10) % n);
	        }
	}

}