首页 > 试题广场 > 数字序列第n位的值
[编程题]数字序列第n位的值
  • 热度指数:7364 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有一个无限长的数字序列1,2,2,3,3,3,4,4,4,4,5,5,5,5,5。。。(数字序列从1开始递增,且数字k在该序列中正好出现k次),求第n项是多少

输入描述:
输入为一个整数n


输出描述:
输出一个整数,即第n项的值
示例1

输入

4

输出

3

备注:
如:输入为3,有序数列第3项的值为2,则输出为2
等差数列类问题,1 22 333 444 ..是等差数列: 1 2 3 4 ... n(即n代表的就是当前数字出现的次数),由等差数列求和公式,只需要有S = (1 + i)*i/2 >= n 即可求出i了,i就是当前的答案
 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input  = new Scanner(System.in);
        int n = Integer.parseInt(input.nextLine());
        
        for (int i = 1; i <= n; i++) {
            if ((1 + i) * i / 2 >= n) {
                System.out.println(i);
                break;
            }
        }
        
    }
}

发表于 2019-09-12 14:03:17 回复(0)

n = int(input())
i=0
while n>0:
    i=i+1
    n=n-i
print(i)

发表于 2019-09-21 21:02:03 回复(0)
Java解答
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int i = input.nextInt();
        int n = 1;
        while(i>0){
            i = i-n;
            n++;
        }
        System.out.println(n-1);
    }
}

编辑于 2019-08-02 19:47:48 回复(0)
#include<iostream>
using namespace std;
int main(){
    int n, i = 1, count = 1;
    cin >> n;
    while(count < n){
       i++;                     //i相当于层数,可想象成杨辉三角那种形状
       count += i;
    }
    cout << i << endl;
    return 0;
}
发表于 2019-08-01 09:09:41 回复(0)
"""
有规律的序列问题
"""
import sys
import math

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    n = int(input().strip())
    t = int(math.sqrt(2 * n))
    while t * (t + 1) >> 1 < n:
        t += 1
    print(t)

发表于 2019-07-10 13:24:03 回复(0)
#include <iostream>
#include <vector>
using namespace std;
// 1 2 2 3 3 3 4 4 4 4......
int main(){
    int n;
    int low = 1, high = 1;  // [low ,high]卡范围
    int ct = 1;             // 计数
    vector<int> res;        // 装数
    res.push_back(1);
    cin >> n;
    while( !(n >= low && n <= high)){  //直到n出现在某个数的范围内
        low += ct;  //2 4 7
        ++ct;       //2 3 4
        high += ct; //3 6 10
        res.push_back(ct); //每一个范围就装一个数
    }
    int len = res.size() - 1;
    cout << res[len] << endl;
    return 0;
}
编辑于 2020-05-18 22:46:07 回复(0)
//如:输入为3,有序数列第3项的值为2,则输出为2
/*
等差求和公式1+2+3+4+5+6+7+8+9
有这个规律可知,当输入的n在i*(i+1)/2与(i+1)*(i+2)/2之间的时候,第n项的值就是i+1
最后我们进行了除2的优化,减少了循环次数
*/
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int flag = 0;
        for(int i = 0;i<= n/2;i++){
            int min = i*(i+1);
            int max = (i+1)*(i+2);
            if(min < 2*n && max >=2*n){
                flag = i+1;break;
            }
        }
        System.out.println(flag);
    }
}

发表于 2020-04-18 16:12:16 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int j=1;
        while (j*(j+1)/2<i ){
            j++;
        }
        System.out.println(j);
    }
}

发表于 2020-02-28 21:40:15 回复(0)

常数时间复杂度解决。

import java.util.*;
/*
等差数列的前n项和问题:
从1到数字k一共出现了(1+k)k/2项
令(1+k)k/2=n,解k的值
(1+k)k=2n
当n=1时,k=1
当n>1时,求pow(2n,0.5),得出的结果一定介于k和k+1之间,向下取整就求出k
这时候进行一步验证,若(k+1)k/2>=n,说明第n项就是k,否则第n项是k+1
*/
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if (n == 1) {
            System.out.println(1);
            return;
        }

        // 把n转为double运算,结果再取整数部分
        int k = (int)Math.pow(2.0 * n, 0.5);
        if (k * (k + 1) >= 2 * n) {
            System.out.println(k);
        } else {
            System.out.println(k + 1);
        }
    }
}
发表于 2020-02-18 12:37:23 回复(0)
#include <iostream>

int main()
{
    int num = 0;
    while(std::cin >> num)
    {
        int i = 0;
        int sum = 0;
        while(sum < num)
        {
            i++;
            sum += i;
        }
        std::cout << i << std::endl;
    }
}

发表于 2020-02-03 19:29:34 回复(0)
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int temp = 0;
    for(int i =1;n>0;i++)
    {
        temp++;
        n = n-i;
    }
    cout << temp << endl;
    return 0;
}

发表于 2019-11-01 17:23:49 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n = 0;
    cin >> n;
    int tem = n;
    for (int i=1; i<=n; ++i) {
        if (tem <= i) {
            cout << i << endl;
            break;
        }
        tem -= i;
    }
    return 0;
}

发表于 2019-10-19 14:00:23 回复(0)
#include <bits/stdc++.h>

using namespace std;

int main(){
  long long k;
  cin >> k;
  long long l = 1, r = 1000000, res = r;
  while(l <= r){
    long long mid = (l + r) >> 1;
    if((mid * (mid + 1)) / 2 >= k){
      r = mid - 1;
      res = min(res, mid);
    } else {
      l = mid + 1;
    }
  }
  cout << res << "\n";
  return 0;
}

发表于 2019-09-09 12:26:04 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        n--;
        double a=1,b=-1,c=-2*n;
        cout<<floor((-b+sqrt(b*b-4*a*c))/(2*a))<<endl;
    }
    return 0;
}

发表于 2019-09-01 16:06:45 回复(0)

从1-n的个数就是(n+1)*n/2个,相当于解一元二次方程,最后求大于等于正数解的正数(相当于上界)。
公式法解一元二次方程。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            //(n+1)*n/2
            System.out.println((int)Math.ceil((-1 + Math.sqrt(1 + 8 * n)) / 2));
        }
    }
}
发表于 2019-08-29 13:58:12 回复(0)
'''
考虑斐波那契数列
第n个数,就是不大于n的斐波那契数列和的后一个数'''

import sys
if __name__=='__main__':
    n = int(input())
    i = 1
    res = 0
    while res < n:
        res += i
        i +=1
    print(i-1)

发表于 2019-08-09 21:21:37 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        //dp[i]表示数字为i一共有多少个数字
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + i;
            if (dp[i] >= n) {
                System.out.println(i);
                return;
            }
        }
    }
}
发表于 2019-08-05 19:13:33 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 1; ; i++) {
            if (n <= i * (i + 1) / 2) {
                System.out.println(i);
                break;
            }
        }
    }
}
发表于 2019-07-02 15:18:03 回复(0)
#include<iostream>
using namespace std;
int main()
{
    int n,i=1;
    cin>>n;
    while((n -= i ++) > 0);
    cout<<i-1<<endl;
    return 0;
}

发表于 2019-07-02 10:56:56 回复(0)
#include <stdio.h>
int main(){
    int n,i=0;
    scanf("%d",&n);
    while(n>((i+1)*i)/2)
        i++;
    printf("%d\n",i);
    return 0;
}

发表于 2018-11-18 12:18:23 回复(0)