有一个无限长的数字序列1,2,2,3,3,3,4,4,4,4,5,5,5,5,5。。。(数字序列从1开始递增,且数字k在该序列中正好出现k次),求第n项是多少
数据范围:
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; } } } }
n = int(input()) i=0 while n>0: i=i+1 n=n-i print(i)
#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; }
//如:输入为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); } }
常数时间复杂度解决。
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); } } }
#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; }
#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; }
从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)); } } }
''' 考虑斐波那契数列 第n个数,就是不大于n的斐波那契数列和的后一个数''' import sys if __name__=='__main__': n = int(input()) i = 1 res = 0 while res < n: res += i i +=1 print(i-1)
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; } } } }