首页 > 试题广场 >

数列计算

[编程题]数列计算

热度指数：1682 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知一个正整数n，(3 <= n <= 15)，将所有n的乘方幂以及所有n的乘方幂（有限个且互不相等）之和组成一个递增序列。例如，当n为4时，该序列为：
1, 4, 5, 16, 17, 20, 21……
(4^0, 4^1, 4^0+4^1, 4^2, 4^0+4^2, 4^1+4^2, 4^0+4^1+4^2……)
请求出该序列的第K项(10进制)。

输入描述:

输入只有1行，为2个正整数，两数之间用一个空格隔开：
n K
(n, K的含义与上述描述一致, 且3<=n<=15, 10<=K<=1000)。

输出描述:

输出为计算结果，为一个正整数（注意在所有测试数据中，结果均不会超过2.1*10^9）。整数前不要有空格或其他任何符号。

示例1

输入

3 100

输出

算法知识视频讲解

Java

LHC0512

Java解法

import java.util.Scanner;

public class Main {

 //就是将k转成2进制，比如k=6，n=4,k的2进制为110，然后以n进制输出来。即1*4^2+1*4^1+0*4^0
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //进制基数
        int n = scanner.nextInt();
        //第k个数
        int k = scanner.nextInt();
        //转化为二进制字符串
        String s = Integer.toBinaryString(k);
        int sum=0;
        for (int i = 0,len=s.length(); i <len; i++) {
            int bit=s.charAt(i)=='1'?1:0;
            sum+=bit*Math.pow(n,len-i-1);
        }
        System.out.println(sum);
    }
}

发表于 2020-03-01 10:02:04 回复(0)

幻想客

//先上代码 利用位运算解决 #include <iostream>
#include <algorithm>
using namespace std;

int main(){
int n,k;
cin>>n>>k;
int res=0;
for(int i=0;i<10;i++){   //因为k小于1000 所以它的位数不会超过10（2*10=1024），所以循环10次就足够了     if((k&1)==1)   //k和1与运算 判断个位数上的数字是否为1
         res+=pow(n,i); //将每次的计算结果放入res中
    K=K>>1;     //k右移 用来下次循环 比较下一位上的数字
}
cout<<res<<endl;//最终输出的res值就是k转换为n进制后的值 也就是第k项的值
}

就是找规律，多测试一些数据就会发现这样一个规律：输入n，k 将k转换为要求的进制（这里为10进制），然后将k转化为n进制输出，该值就是该序列的第k项的值。比如n=4，k=6 k的十进制为 110 第k项的值就为 4*0+4*1+4*2=20

还有一点，我认为这道题本身也有些问题，因为这道题目要求k是大于10的，而我将这个限制条件加入到代码中时，就会报错，提示说某个测试数据不通过（例如n=4，k=7）也就是说该题的后台测试数据有k<10的数据，所以这道题我猜测是默认k>0的。（纯属个人见解）

发表于 2019-08-03 16:58:31 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,s=0;
    cin>>n>>k;
    for(int i=0;i<10;i++){
        if(k&1)
            s += pow(n, i);
        k>>=1;
    }
    cout<<s<<endl;
    return 0;
}

发表于 2019-10-28 01:08:22 回复(0)

YQ520

//不用转换成2进制的方法

//乘方幂次 j 增加1，项数增加2^j个，所以算出第K项是第几个乘方。用递归的方法求解

#include<iostream>

usingnamespacestd;

class jscf {

public:
    int js(int n, int K) {
        if (K == 0) return 0;
        if (K == 1) return 1;
        int sumk = 0;
        int temp = 0, j = 0, m = 0;
        for (int i = 0; i <= 10; i++) {
            temp = sumk;
            sumk = sumk + pow(2, i);
            if (temp <= K&&K <= sumk) {
                j = i; //算出是第几个乘方
                m = K - temp-1; //算出在该乘方中是第几个数，是第几个数就加上第几项的值
                break;
            }
        }
        return pow(n, j) + js(n, m); //递归算出第K项的值
    }
};
int main() {
    jscf test1;
  int n, K;
    cin >> n>>K;
    int b = test1.js(n, K);
    cout << b;
}

发表于 2019-09-02 18:15:37 回复(0)

C/C++

gossipkasper

就是将k转成2进制，比如k=6，n=4,k的2进制为110，然后以n进制输出来。即1*4²+1*4¹+0*4⁰

#include<bits/stdc++.h>
using namespace std;
int main(){


int n,k;
cin>>n>>k;
    vector<int> m;
int res=0;
for(int i=10;i>=0;i--){   //因为k小于1000 所以它的位数不会超过10（2*10=1024），所以循环10次就足够了     if((k&1)==1)   //k和1与运算 判断个位数上的数字是否为1
         m.push_back((k>>i)&1); //将k转换成2进制
       // //cout<<( (k>>i) & 1);//输出二进制
}
    for(int j=10;j>=0;j--){
        res=res+m[j] * pow(n,10-j);
    }
cout<<res<<endl;//最终输出的res值就是k转换为n进制后的值 也就是第k项的值
    return 0;
}

发表于 2019-08-14 18:05:51 回复(0)

Java

阿里巴巴本地生活内推

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int c = 0;
        int i = 0;
        int[] arr = new int[k];
        while(c<k){
            int tmp = (int) Math.pow(n,i++);
            arr[c++] = tmp;
            int len = c;
            for(int j=0;j< len-1 ;j++){
                 if(c>=k){
                    break;
                }
                arr[c++] = tmp + arr[j];
            }
        }
        Arrays.sort(arr);
        System.out.println(arr[k-1]);
    } 
}

发表于 2022-04-19 21:19:30 回复(0)

Java

lmz9509

/*
思路：将k变成二进制后，对应位上为1则表明n的次数
例如： n = 4, k = 5
由于 5 的二进制数为 101
那么对应的数
n^0 + n^2
k = 6 --- 110
n^1 + n^2
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        String bin = Integer.toBinaryString(k);
        int sum = 0;
        for(int i = bin.length()-1,j = 0;i>=0;i--){
            int temp = (bin.charAt(i) == '1')?1:0;
            sum = sum + temp*(int)Math.pow(n,j++);
        }
        System.out.println(sum);
        
    }
}

发表于 2020-05-21 15:32:16 回复(0)

夏花爱秋叶

var line=readline().split(' ').map(Number);
var num=line[0];
var k=line[1];
// 使用一个数组存储,第一个数设置0是为了方便k
var arr=[0];
var j=1
for(var i=1;i<=k;i++){
    if(i==1){
        arr.push(1)
    }else if(Math.pow(2,j)==i){
        // 在第2,4,8,16项的时候进行
        arr.push(Math.pow(num,j));
        j++;
    }else{
        // 在其他时候，其他项=前面的项逐个+第二种情况
        arr.push(arr[i-Math.pow(2,j-1)]+arr[Math.pow(2,j-1)])
    }
}
console.log(arr[arr.length-1])

发表于 2020-04-07 21:53:31 回复(0)

Python

watle自动机

没看标签，直接考虑了DP解法

def getList(n, k):
    dp = [0] * (k + 1); dp[1] = 1;
    i = 2
    while i <= k:
        dp[i] = dp[i // 2] * n; i *= 2
    if dp[k] != 0:
        return dp[k]
    else:
        i = 3;
        while i <= k:
            start, end = 1, i - 1
            while i <= k and start < end:
                if dp[i] == 0:
                    dp[i] = dp[start] + dp[end]; i += 1; start += 1
            i += 1
        return dp[k]
    
if __name__ == "__main__":
    num = str(input()).split(" ")
    n, k = int(num[0]), int(num[1])
    print(getList(n, k))

发表于 2020-01-07 23:30:01 回复(0)

勇者201911211415382

#include <iostream>
#include <math.h>
using namespace std;
typedef unsigned int uint;
uint counting(uint k,const uint n)
{
    uint sum = 0;
    uint temp;
    if(k > 1000 || k < 10 || n < 3 || n> 15)//去除错误输入
        return 0;
    //求和n^0*temp + n^1*temp +...+ n^9*temp
    for(int i=0;i < 10; ++i)//k最大可取1023,10次
    {
        temp = k & 0x0001;//取最后一位的值 0 或 1
        sum += (uint)pow((double)n,(double)i)*temp;
        k = k >> 1;//右移一位
    }
    return sum;
}
int main()
{
    uint n,K,rec;
    cin >> n >> K;
    rec = counting(K,n);
    cout << rec;
    return 0;
}

这题挺唬人的

发表于 2019-11-21 21:52:54 回复(0)

今天减肥了吗

#include <iostream>
#include "string.h"
#include "vector"
#include <math.h>

using namespace std;

int main()
{
	int n, k;
	cin >> n>> k;
	vector<int> m;
	int nRes=0;
	for (int i = 0; i <= 10;i++)
	{
		m.push_back((k >> i) & 1); // 判断移位以后最低位是1还是0
	}
	for (int i = 0; i <= 10;i++)
	{
		nRes += m[i] * pow(n, i);
	}
	cout << nRes;
	system("pause");
	return 0;
}

发表于 2019-10-18 15:14:24 回复(0)

嗦鹅

一个找规律的题，直接转二进制解决

import sys
import math
m,n = map(int,input().strip().split())
s1 =(bin(n))[2:]
s2 = len(s1)
number = 0
for i in range(s2):
if s1[i]=='1':
number = m**(s2-i-1)+number
print(number)

发表于 2019-09-13 20:57:48 回复(0)

cy助我

# 找规律 第k个数 k的二进制中1的形式 为指数
n, k = list(map(int,input().strip().split()))
kb_str = bin(k)[2:][::-1] # 如bin(5)-->'0b101'
t = 0
res = 0
for i in range(len(kb_str)):
    if kb_str[i] == "1":
        res += pow(n,t)
    t += 1
print(res)

发表于 2019-07-28 18:45:58 回复(0)

白色纯度


	import math
a, n = list(map(int,input().split()))
k = int(math.log(n,2))
res = 0
for i in range(k,-1,-1):
    count = n // (2**i)
    if count == 1:
        res += a**i
    n %= 2**i
print(res)

大家可以参考这篇博客，很容易就能写出代码。 https://blog.csdn.net/weixin_42564710/article/details/96498350

编辑于 2019-07-19 21:06:07 回复(0)

sea_sid

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        //k的二进制表达，权重为n
        int n = Integer.parseInt(temp[0]), k = Integer.parseInt(temp[1]);
        int ans = 0, val = 1;
        while(k!=0){
            ans += (k&1)*val;
            k >>= 1;
            val *= n;
        }
        System.out.println(ans);
    }
}

发表于 2019-07-05 19:39:59 回复(0)