首页 > 专题系列 > Java解POJ > POJ 1316 Self Numbers [解题报告] Java
2013
11-09

POJ 1316 Self Numbers [解题报告] Java

Self Numbers

问题描述 :

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), …. For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, …

The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.

输入:

No input for this problem.

输出:

Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.

样例输入:


样例输出:

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

解题代码:

(1)
 public class Main{
   public static void main(String args[]){
      setNumbers();
   }
   public static void setNumbers(){ 

    int[] numbers=new int[10000]; 
     //Arrays.fill(numbers, 0); 
     for(int i=1;i< 10000;i++){
       int temp = i+i%10+(i/10)%10+(i/100)%10+i/1000; 
               if(temp< 10000) 
                   numbers[temp]=1;  
            } 
             for(int i=1;i< 9999;i++){
                     if(numbers[i]==0)  
                          System.out.println(i); 
             }  
     }
}

(2)
//* @author popop0p0popo
public class Main{
	public static void main(String[] args){
		int[] n=new int[9999];
		for (int i=0;i< n.length ;i++ ){
			n[i]=getN(i+1);
		}
		intSort(n,0,n.length-1);
		System.out.println(1);
		for (int i=0;i< n.length-1 ;i++ ){
			if (n[i]+1>9993){
				break;
			}
			for (int j=n[i]+1;j< n[i+1] ;j++ ){
				System.out.println(j);
			}
		}
	}

	public static int getN(int n){
		int a=n/1000;
		int b=(n-1000*a)/100;
		int c=(n-1000*a-100*b)/10;
		int d=n-1000*a-100*b-10*c;
		return n+a+b+c+d;
	}

	public static void intSort(int[] number,int left,int right){
        if (left< right){
            int s=number[(left+right)/2];
            int i=left-1;
            int j=right+1;
            while (true){
                while (number[++i]< s);
                while (number[--j]>s);
                if (i>=j) break;
                swap(number,i,j);
            }
            intSort(number,left,i-1);
            intSort(number,j+1,right);
        }
    }

	public static void swap(int[] number,int i,int j) {
        int t;
        t=number[i];
        number[i]=number[j];
        number[j]=t;
    }
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。