问题描述

JAVA算法训练 数列给定一个正整数k(3≤k≤15)

------------------题目-------------------------------------------------------
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
　　1，3，4，9，10，12，13，…
　　（该序列实际上就是：3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2，3^0+3^1+3^2，…）
　　请你求出这个序列的第N项的值（用10进制数表示）。

　　例如，对于k=3，N=100，正确答案应该是981。

感觉看不懂题目序列的规律（把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列） ，然后上百度给的答案是要转2进制再求，求大神解惑。新人币不多

---------------代码------------------------------
public static void main (String args[])throws IOException{
long a[]=new long[1001];
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
String s[]=bf.readLine().split(" ");
int k=Integer.parseInt(s[0]);
int n=Integer.parseInt(s[1]);
int m=1;
int sum=0;
while(n>0){
a[m++]=n%2;
n=n/2;
}
m--;
for(int i=1;i<=m;i++){
sum+=a[i]*add(k,i-1);
System.out.println(a[i]+" "+add(k,i-1)+" "+sum);
}
System.out.println(sum);
}
static int add(int k,int n){
int sum=1;
for(int i=1;i<=n;i++)
sum*=k;
return sum;
}
}
-------------------运行结果------------------------------
3 100
0 1 0
0 3 0
1 9 9
0 27 9
0 81 9
1 243 252
1 729 981
981

解决方案

本来就是转换成二进制来做。
假设二进制的每一位表示 (N-1)^对应位数 是否包含在和中。
比如
当k=3时
0001表示3^0存在
0010表示3^1存在
0011表示3^0和3^1存在
0100表示3^2存在
0101表示3^2和3^0存在
...
这个序列也就是1 2 3 4 5...的二进制表示
所以从1~N输出下就可以了。