林惜城


私信TA

用户名:reminder

访问量:5875

签 名:

等  级
排  名 244
经  验 4868
参赛次数 0
文章发表 95
年  龄 0
在职情况 学生
学  校 西安电子科技大学
专  业

  自我简介:

哈姆


解题思路:

(1)观察序列:30,31,30+31,32,30+32,31+32,30+31+32,…

(2)发现可以写成:30*1,31*1+30*0,31*1+30*1,32*1+31*0+30*0,32*1+31*0+30*1,32*1+31*1+30*0,32*1+31*1+30*1,…

(3)对于数列中的每一个数,都可以表示为一系列3m*(1 or 0)的形式。

(4)多项式中的1和0提取出来,就是1,10,11,100,101,110,111,…即原数列中数的位置的二进制表示,第1个数对应1,第2个数对应10,第3个数对应11,……

(5)至于指数 m ,它的大小是和二进制的位数有关的,最低位对应 m = 0,之后随着位数递增。

(6)理解了数列的表示方式,就可以写出底数为 k 的数列的第 N 项了,就是把 N 写成二进制,每位乘以对应的 k 的方幂,再求和就得到了结果。


注意事项:

(1)int k, N, res, order; 这句编译时会把除了 order 以外的变量初始化为0,而 order 初始化为51,必须在定义时就初始化 order = 0 才行,我无法理解。
(2)求方幂用 pow() 函数的话会报答案错误,只能写成用 for 循环累乘的形式,我没开会员所以不知道为啥错了。


参考代码:

// 题目 1105: 数列
#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int k, N;
	cin >> k >> N;
	int res = 0;   // 最后结果
	int order = 0; // 数位,代表幂,从 0 开始
	while (N) {
		if(N % 2 == 1) {
			// res += pow(k, order); //用 pow() 会报答案错误???
			int temp = 1;
			for (int i = 0; i < order; ++i) {
				temp *= k;
			}
			res += temp; // 如果二进制N的最低位是1,则加上对应的数字
		}
		N /= 2;  // 舍去最低位
		++order; // 位数+1
	}
	cout << res << endl;
	return 0;
}


 

0.0分

1 人评分

  评论区