2 a1394393468 a1394393468 于 2016.03.01 19:39 提问

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

1个回答

caozhy
caozhy   Ds   Rxr 2016.03.01 20:05
已采纳

本来就是转换成二进制来做。
假设二进制的每一位表示 (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输出下就可以了。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!