我要招人

去企业版

首页 > 试题广场 >

疯狂序列

[编程题]疯狂序列

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

东东从京京那里了解到有一个无限长的数字序列: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...(数字k在该序列中正好出现k次)。东东想知道这个数字序列的第n项是多少,你能帮帮他么

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10^18)

输出描述:

输出一个整数,即数字序列的第n项

示例1

输入

输出

算法知识视频讲解

~~~~！

result = ((8*n+1)**0.5-1)/2  if result == int(result):     print int(result) else:     print int(result)+1

假设第n项为k，从一加到k的值应该是sum=(k-1)*k/2，这个数可能大于或等于n。如果n小于sum，那么解方程x^2+x-2n=0，x的值会在k-1和k之间，向上取整就是k了。解二次方程，x=[sqrt(8n+1)-1]/2（当然要选较大的解，另一个较小的解是小于0的）。如果x的解是整数，正好就是k；否则，x+1是k

发表于 2018-07-25 22:19:04 回复(1)

Johnny、111

import math
if __name__=='__main__':
x=int(input())
a=(-1+math.sqrt(1+8*x))/2
y=math.ceil(a)
print(y)

发表于 2018-08-01 22:08:57 回复(0)

ErgouJing

#include<iostream>
using namespace std;
int main()
{
    long long n = 0;
    cin >> n;
    long long i;
    for(i = 1; n > 0; i++)
    {
        n -= i;
    }
    cout << i - 1;
    return 0;
}

编辑于 2018-07-31 20:12:01 回复(4)

一直走201903111706936

第一项：1 —— 占1个序列
第二项：2 2 ——占2个序列
第三项：3 3 3  ——占3个序列
···
第k项： k1 k2 k3 ···  kk ——占k个序列
求第169个序列所在第几项？
故求第n个序列就是求第k项的前k项和，由是等差数列，n=k(k+1)/2,
因为第k项不管是k几序列，算出的都是小于或等于k的，故向上取整。

代码实现：

    // 整体排序
    function getItem01(num) {
      return Math.ceil((Math.sqrt(1 + 8 * num) - 1) / 2)
    }
    console.log(getItem01(169)); // 18

    // 顺序算法
    function getItem02(num) {
      for(let i = 1; i < num; i++) {
        if(i * (i - 1) / 2 <= num && i * (i + 1) / 2 >= num) {
          return i;
        }
      }
    }
    console.log(getItem02(169)); // 18

编辑于 2019-03-12 11:21:06 回复(0)

午光

import math
n = int(input())
print(math.ceil((2*n+0.25)**0.5-0.5))

$\frac{k(k+1$ , 则 $k = \sqrt{2n+1/4}-1/2$ ，算出来的结果向上取整。
```

编辑于 2018-05-20 21:47:59 回复(0)

CultyZoo

d = int(input())
# 求n
l = int((2*d) ** 0.5) - 1
r = int((2*d) ** 0.5)+1 + 1
res = None
for i in range(l, r):
    if i**2 - i < 2*d and i**2 + i >= 2*d:
        res = i
        break
print(res)

放缩法解

n*(n-1) < 2*d <= n*(n+1) / 2

(n-1) ** 2 < 2*d < (n+1) ** 2

利用不等式缩小搜索的范围

发表于 2021-10-07 00:19:00 回复(0)

牛客188000430号

#include<iostream>
using namespace std;
int main()
{
long long n = 0;
cin >> n;
long long i=1;
while(n > 0)
{
n = n - i;
i++;
}
cout << i - 1;
return 0;
}

发表于 2020-06-22 22:34:08 回复(1)

Python

黄颖待

def seq_num(num):
    flag = True
    x = 0.0
    while flag:
        if num<=((x+1)*x)/2:
            flag = False
        else:
            x+=1
    return int(x)
seq_num(num)

发表于 2020-04-26 14:23:28 回复(0)

beautiful-girl

我在自己的ide里测试通过，，在这里就不行

importmath

x =input

ifx > 0:

print(int((1+math.sqrt(8*x-7))/2))

else:

print(1)

发表于 2019-08-23 16:02:41 回复(0)

offer++++++

import math
n = int(input("请输入："))
k = math.sqrt(2*n + 1/4) - 1/2
print(math.ceil(k))

发表于 2018-12-11 09:22:57 回复(0)

YOUNGGGG

各位请教下，使用c语言为什么编译不成功，而在VC++6.0上可以？

#include <stdio.h>
int main(){
    int n;
    scanf("%d"&n);
    for(int i = 1; n > 0; i++){
        n = n-i；
    }
    printf("%d\n",i-1)；
    return 0;
}

编辑于 2018-09-11 22:01:40 回复(1)

PrettySunshine2018

求解释，为什么它是个等差数列？我看不出来

发表于 2018-09-09 21:37:55 回复(1)

ring201807131322254

import math

n=int(input())

print (math.ceil((2*n+0.25)**0.5-0.5))

发表于 2018-08-28 18:19:10 回复(0)

Typole

找关系！！！等差数列，前n项和！！！如果索引从0起，则n-1项和的位置为第n项的第一个数。

发表于 2018-06-14 20:06:43 回复(0)

禅音当妖七

import math
n = int(input())
m = (math.sqrt(1+8*n)-1)/2
print(math.ceil(m))

编辑于 2018-05-22 17:16:38 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师数据分析工程师算法工程师京东 2018 PHP工程师数学 Java工程师

上传者：小小

难度：

15条回答 75收藏 7179浏览

通过挑战的用户

牛客44979...

2022-09-29 22:11:24
牛客59044...

2022-09-01 20:12:27
牛客19391...

2022-08-26 22:45:16
牛客53602...

2022-08-26 11:36:53
0朝花夕拾

2022-07-25 00:46:35

疯狂序列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题