精华内容
下载资源
问答
  • 从一个取值范围为1~N的不重复数列中找出所有满足两数和为N+1的数 题目:一个整数数列,元素取值可能是1~NN是一个较大的正整数)的任意一个数,相同数值不会重复出现。设计一个算法,找出数列中符合条件的...

    转载:http://blog.csdn.net/wcyoot/article/details/6436304


    从一个取值范围为1~N的不重复数列中找出所有满足两数和为N+1的数对


    题目:一个整数数列,元素取值可能是1~N(N是一个较大的正整数)中的任意一个数,相同数值不会重复出现。设计一个算法,找出数列中符合条件的数对的个数,满足数对中两数的和等于N+1。复杂度最好是O(n),如果是O(n2)则不得分。

     


    算法:建立一个map<数列元素值, 对应索引>. 对每个元素i,如果N+1-i不在map中,插入i,否则输出(i, map[i]).复杂度O(n).

     

    #include <map>
    // ar为不重复的数列,输出ar中所有两数和为N的数对
    void PrintPairs(const std::vector<int>& ar, int N)
    {
    	std::map<int, int> nodemap; // <数值,位置>
    	for(size_t i = 0; i < ar.size(); ++i)
    	{
    		std::map<int, int>::const_iterator iter = nodemap.find(N - ar[i]);
    		if(iter == nodemap.end())
    			nodemap[ar[i]] = i;
    		else
    		{
    			printf("找到数对(%d, %d)/n", ar[iter->second], ar[i]);
    		}
    	}
    }

    展开全文
  • 斐波那契数列n

    2020-04-02 15:37:03
    在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。 给定整数n,求Fibn mod10000。 输入格式 输入包含多组测试用例。 每个测试用例占一行,包含一个整数n。 当输入用例n=-1时,表示输入终止,且该用例...

    1:斐波那契数列第n项
    在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。

    给定整数n,求Fibn mod10000。

    输入格式
    输入包含多组测试用例。

    每个测试用例占一行,包含一个整数n。

    当输入用例n=-1时,表示输入终止,且该用例无需处理。

    输出格式
    每个测试用例输出一个整数表示结果。

    每个结果占一行。

    数据范围
    0≤n≤2∗109
    输入样例:
    0
    9
    999999999
    1000000000
    -1
    输出样例:
    0
    34
    626
    6875

    思路:矩阵快速幂 , 每次取模 。

    #include <stdio.h>
    #include <string.h>
    long long n,mod=10000;
    void Matrix1(long long a[2],long long b[2][2])
    {
    	long long c[2]={0};
    	for(int j=0;j<2;j++)
    		{
    			for(int k=0;k<2;k++)
    			{
    				c[j]=(c[j]+a[k]*b[k][j]%mod)%mod;
    			}
    		}
    		memcpy(a,c,sizeof(c));
    }
    void Matrix2(long long b[2][2])
    {
    	long long c[2][2]={0};
    	for(int i=0;i<2;i++)
    	{
    		for(int j=0;j<2;j++)
    		{
    			for(int k=0;k<2;k++)
    			{
    				c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod;
    			}
    		 } 
    	}
    	memcpy(b,c,sizeof(c));
    }
    int main()
    {
    	while(~scanf("%lld",&n))
        {   
            if(n==-1) break;
            else
            {  
                long long a[2]={0,1};
                long long b[2][2]={0,1,1,1};
    	        while(n)
    	        {
    		    if(n&1)	Matrix1(a,b);
    		    Matrix2(b);
    		    n>>=1;
    	        }
    	    printf("%lld\n",a[0]);
            }
        }
        return 0;
    }
    

    2:斐波那契数列 10’
    描述
    已知斐波那契数列 1,1,2,3,5,8,13,21每一项是前两项的和。

    请告诉laofu,第202003281331项的最后一位是多少。(大家写到这题,是不是这个时间呢,嘿嘿~)

    例如:第八项的最后一位是1

    【答案提交】

    这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个数字,填写多余的内容将无法得分。

    思路:最后一位只和最后一位有关,所以每次模10取最后一位。

    #include <stdio.h>
    #include <string.h>
    long long n,mod=10,a[2]={0,1},b[2][2]={0,1,1,1};
    void Matrix1(long long a[2],long long b[2][2])
    {
    	long long c[2]={0};
    	for(int j=0;j<2;j++)
    		{
    			for(int k=0;k<2;k++)
    			{
    				c[j]=(c[j]+a[k]*b[k][j]%mod)%mod;
    			}
    		}
    		memcpy(a,c,sizeof(c));
    }
    void Matrix2(long long b[2][2])
    {
    	long long c[2][2]={0};
    	for(int i=0;i<2;i++)
    	{
    		for(int j=0;j<2;j++)
    		{
    			for(int k=0;k<2;k++)
    			{
    				c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod;
    			}
    		 } 
    	}
    	memcpy(b,c,sizeof(c));
    }
    int main()
    {
    	scanf("%lld",&n);
        while(n)
    	   {
    		  if(n&1)	Matrix1(a,b);
    		  Matrix2(b);
    		  n>>=1;
    	   }
        printf("%lld\n",a[0]);
        return 0;
    }
    
    展开全文
  • 设计一个算法,找出数列中符合条件的数的个数,满足数对中两数的和等于N+1。复杂度最好是O(n),如果是O(n2)则不得分。   算法:建立一个map. 每个元素i,如果N+1-i不在map,插入i,否则输出(i, map...

    题目:一个整数数列,元素取值可能是1~N(N是一个较大的正整数)中的任意一个数,相同数值不会重复出现。设计一个算法,找出数列中符合条件的数对的个数,满足数对中两数的和等于N+1。复杂度最好是O(n),如果是O(n2)则不得分。

     


    算法:建立一个map<数列元素值, 对应索引>. 对每个元素i,如果N+1-i不在map中,插入i,否则输出(i, map[i]).复杂度O(n).

     

    [cpp]  view plain copy
    1. #include <map>  
    2. // ar为不重复的数列,输出ar中所有两数和为N的数对  
    3. void PrintPairs(const std::vector<int>& ar, int N)  
    4. {  
    5.     std::map<intint> nodemap;  
    6.     for(size_t i = 0; i < ar.size(); ++i)  
    7.     {  
    8.         std::map<intint>::const_iterator iter = nodemap.find(N - ar[i]);  
    9.         if(iter == nodemap.end())  
    10.             nodemap[i] = ar[i];  
    11.         else  
    12.         {  
    13.             printf("找到数对(%d, %d)/n", ar[iter->second], ar[i]);  
    14.         }  
    15.     }  
    16. }  
     

     

    PS:可参考:http://blog.csdn.net/wcyoot/archive/2011/05/21/6435904.aspx

    展开全文
  • 逆序对数列

    2016-10-05 06:37:41
    【题目描述】 对于一个数列{a[]},如果有ia[j],那么我们称a[i]与a[j]为一对逆序对数。若对于任意一个由1~n自然数...写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数10000求余数后的
    【题目描述】
    

    对于一个数列{a[]},如果有i<j且a[i]>a[j],那么我们称a[i]与a[j]为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序对数。询问逆序对数为k的这样自然数数列到底有多少个。

    【输入描述】

     第一行为两个整数n、k。

    【输出描述】

    写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

    【输入样例】

    4 1

    【输出样例】

    3

    【数据范围】

    下列3个数列逆序对数都为1,分别是:

    1 2 4 3

    1 3 2 4

    2 1 3 4
    n <= 1000,k <= 1000。

     

    BZOJ的数据太水了,O(m*n^2)的普通解法竟然过了:

    源代码:
    
    #include<cstdio>
    int m,n,f[1001][1001]={0};
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int a=1;a<=n;a++) //初始化边界。
          f[a][0]=1;
        for (int a=1;a<=n;a++)
          for (int b=1;b<=m;b++)
            for (int c=1;c<=a;c++)
              if (b-a+c>=0) //避免越界溢出。
                f[a][b]=(f[a][b]+f[a-1][b-a+c])%10000;
        printf("%d",f[n][m]);
        return 0;
    }
    
    /*
        挺简单的DP:
            f[i][j]表示1~i个自然数所组合成的、逆序对数为j的数列个数。
            在1~i中,i即为最大,故将它安插到某一位置,其后方的所有数都会与它形成逆序对。
            由上可得状态转移方程:
                f[i][j] = ∑f[i-1][j-i+k],(1 <= k <= i)。
    */

     

     

    滚动数组+前缀和优化后的O(mn)解法:

    源代码:
    
    #include<cstdio>  
    int m,n,sum[1001],f[1001];
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int a=0;a<=m;a++) //除f[1][0]为1外,f[1][j]皆为0。
          sum[a]=1;
        for (int a=2;a<=n;a++) //直接从f[2][]开始。
        {
            f[0]=1; //f[i][0]显然为1。
            for (int b=1;b<=m;b++)
              if (b-a>=0)
              {
                f[b]=sum[b]-sum[b-a];
                while (f[b]<0) //注意此处理,避免因负数而出现错误。
                  f[b]+=10000;
              }
              else
                f[b]=sum[b];
            for (int b=1;b<=m;b++) //前缀和处理。
              sum[b]=(sum[b-1]+f[b])%10000;
        }
        printf("%d",f[m]);
        return 0;
    }

     

    展开全文
  • 斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)...
  • 求斐波那契数列的第n

    千次阅读 2017-08-16 16:08:54
    提要本文介绍了4种(3种?)求斐波那契数列n项的方法。
  • 斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)...
  • 常用数列范围问题

    2013-03-23 22:51:53
    1. fibnacci数列 f(0)=0 f(1)=1 f(n)=f(n-1)+f(n-2), n>=2 f(46)=1836311903  f(47)=2971215073 可以发现f(47)已经超过了int能表示的范围,要留心。 reference: ...
  • 题目描述大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。n&lt;=39首先在这里先讲讲这个什么是斐波那契数列,斐波那契数列的第一项是0,第二项是1然后从第三项开始每项等于前两项...
  • 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。斐波那契数列的定义如下: ... 题目可以看到,n范围是70,最先想到的递归肯定是不行的,那么我们钻一个空子
  • 一个整数数组,元素取值...设计一个算法,找出数列中符合条件的数的个数,满足数对中两数的和等于N+1; 代码#include void FixedSum(int* a,int n,int d){ for(int i = 0,j = n-1;i<n&&j>=0&&i;){ if(a[i]+a[j])
  • 矩阵快速幂: F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2) (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...) 给出n,求F(n),由于结果很大,输出F...引例 :求斐波那契数列的第 n 项 mod
  • n个素数构成等差数列

    千次阅读 2019-01-24 16:46:03
    n个素数构成等差数列 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Description ...即在1到10的范围内有3个素数构成等差数列的情况有几组解,很显然3,5,7是一组解,也是唯...
  • 要求:第一行输入n m,第二行输入一个数列n数列长度,m为要插入的值,排序后输出,m n为零时退出程序 输入:3 3 1 2 4 0 0 Press any key to continue 输出:1 2 3 4 int main() { int n,m,i,j; int a[100]...
  • ACM模版描述斐波那契数列的定义如下:F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) (n >= 2)(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …) 给出n,求F(n),由于结果很大,输出F(n) % 1000000009...
  • 要求:第一行输入n m,第二行输入一个数列n数列长度,m为要插入的值,排序后输出,m n为零时退出程序运行结果 ↓3 3 1 2 4 1 2 3 4 0 0请按任意键继续. . . #include #include int main(void) { int array...
  • 斐波那契数列:斐波那契数列(Fibonacci sequence),又称黄金分割数列和“兔子数列”在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,nN*),当n趋向于无穷大时...
  • na 斐波那契数列f(f(n))

    千次阅读 2017-09-24 17:04:53
    题目描述: 给出T个n,求斐波那契数列的f(f(n)).(答案取模1e9+7) 数据范围: 100% 1<=n数据好大,那么这题一定有规律。 首先先要了解一个关于斐波切数列的性质,即斐波那契数列 ( 取模...f(f(n)),最后要MOD=1e
  • 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,nN*)。 1. ...
  • } 二、问题描述: 已知斐波那契数列 F​n​​=F​n−1​​+F​n−2​​(n>=3),F​1​​=1,F​2​​=1 求解该数列的第n项,结果998244353取模。 输入格式:输入一个正整数n(1<=n)。 输出格式:输出一个数,表示...
  • 斐波那契数列

    千次阅读 2019-06-11 10:56:29
    请你输出斐波那契数列的前N项(0 < N < 30)。请用循环实现。 输入 输入一个整数N。 输出 输出斐波那契数列的前N项,相邻两项用一个空格隔开。 输入示例 8 输出示例 1 1 2 3 5 8 13 21 数据范围 对于100%的...
  • 如果我们将其中一个数列中所有数都加上一个常数,另外一个数列中所有数都减去一个常数,那么必然也得到一个符合条件的数列,所以我们可以认为这样得到的数列对和原先的数列对是等价的,不在我们考虑范围之内。...
  • 用递归的方式求斐波那契数列的第n个数。用非递归的方式求斐波那契数列的第n个数。定义: 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,...
  • 裴波拉契数列 递归求第N的值

    千次阅读 2009-11-03 17:02:00
    /*RecursionArray.java *裴波拉契数列,如下代码是用递归的方式运算,当N大于50时,速度就很慢了,测试时当N为100 *时,要好几分钟,double类型的取值范围为-1.7E308——1.7E308,且N的值过大为溢出,怎么解决?...
  • NowCoder数列

    千次阅读 2015-05-20 11:00:19
    /*题目描述 NowCoder最近在研究一个数列: ...请你帮忙确认一下数列中n个数是否是3的倍数。 输入描述: 输入包含多组数据。 每组数据包含一个整数n,(0≤n≤1000000)。 输出描述: 对应
  • 数列分段

    2020-03-22 13:22:43
    对于给定的一个长度为n 的正整数数列 ai,现要将其分成连续的若干段,并且每段和不超过 m(可以等于 m),问最少能将其分成多少段使得满足要求。 输入格式 第一行包含两个正整数 n,m,表示了数列的长度与每段和的...
  • 问题描述:一个数列,求这个数列有序后,相邻数字之间最大的差值是多少。思路利用桶排序的过程完成求最大差值问题。已知桶排序过程如下:1、首先基于数据的范围创建相应大小的辅助数组help。即遍历找到数组的最大值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,455
精华内容 19,782
关键字:

对数列中n的范围