头像

自律




离线:19天前



自律
26天前

题目描述

输入一个整数 n ,求斐波那契数列的第 n 项。

假定从0开始,第0项为0。(n<=39)

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C 代码

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    int n;
    int f1,f2,f3;
    int i;
    f1 = 1;
    f2 = 2;
    printf("请输入您需要输入的序列:");
    scanf("%d",&n);
    if (n == 1)
    {
        f3 = 1;
    }
    else if(2 == n)
    {
        f3 = 2;
    }
    else
    {
        for (i = 3;i<=n;++i)
        {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;

        }
    }
    printf("%d",f3);
    return 0;
}


算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C 代码

#include <stdio.h>
#include <stdlib.h>
int fib(int n)
{
    if(n <= 2)
        return 1;
    else if(n>2)
        {
            return fib(n - 1) + fib(n - 2);
        }
    else
        printf("error");
}
int main()
{   int x;
    scanf("%d",&x);
    printf("%d\n",fib(x));
    return 0;
}





自律
28天前

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

int maxsum=0;
int maxsum1(int a[],int n)
{
    int thissum;
    int i,j,k;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
        {
            thissum=0;
            for(k=i;k<=j;k++)
                {
                    thissum+=a[k];
                    if(thissum>maxsum)
                        maxsum=thissum;
                }
        }

        return maxsum;
}
int maxsum2(int a[],int n)
{
    int thissum,i,j;
    for(i=0;i<n;i++)
    {
        thissum=0;
        for(j=i;j<n;j++)
        {
            thissum+=a[j];
            if(thissum>maxsum)
                maxsum=thissum;
        }
    }
    return maxsum;
}
int maxsum3(int a[],int n)
{
    int thissum=0,i;
    for(i=0;i<n;i++)
    {
        thissum+=a[i];      //sum=a[i]+sum>a[i]?sum+a[i]:a[i];
        if(thissum>maxsum)
        maxsum=thissum;
        else if(thissum<0)
        thissum=0;
    }
    return maxsum;
}
int main()
{
    int n,i;
    int a[100];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];                      //时间复杂度 
    maxsum1(a,n);                       //O(n三次方) 
    //maxsum2(a,n);                     //O(n平方) 
    //maxsum3(a,n);                     //O(n) 
    cout<<maxsum;
    return 0;

} 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
1个月前

题目描述

有 N 个瓶子,编号 1∼N,放在架子上。

比如有 5 个瓶子:

2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式
第一行包含一个整数 N,表示瓶子数量。

第二行包含 N 个整数,表示瓶子目前的排列状况。

输出格式
输出一个正整数,表示至少交换多少次,才能完成排序。

数据范围
1≤N≤10000

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int n,i,j,ans=0;
    int a[10000];
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            for(j=1;j<=n;j++)
                if(a[j]==i)
                {
                    a[j]^=a[i];
                    a[i]^=a[j];
                    a[j]^=a[i];
                    ans++;
                }
        }
    }
    cout<<ans;         
    return 0;
}
//最开始用的快速排序,快速排序交换次数不是最少的。此题N个数为1~N,课通过模拟解题。
//参考https://www.acwing.com/solution/content/6983/



算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
1个月前

题目描述

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去,就正好可以表示为 4 个数的平方和。

比如:

5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4 个数排序:

0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//超时了
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n,a,b,c;
    cin >> n;
    double x = sqrt(n),d;
    for(a = 0 ; a <= x;a++)
        for(b = a; b <= x; b++)
            for(c = b ; c <= x ; c++)
            {
               d = sqrt(n - a * a - b * b - c * c);
               if(d == (int)d)
               {
                   cout << a << " " << b << " " << c << " " << d << endl;
                   return 0;
               }

            }
    return 0;
}



算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
1个月前

题目描述

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。

其楼房的编号为 1,2,3…
当排满一行时,从下一行相邻的楼往反方向排号。

比如:当小区排号宽度为 6 时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 .....
我们的问题是:已知了两个楼号 m 和 n,需要求出它们之间的最短移动距离(不能斜线方向移动)。

输入格式
输入共一行,包含三个整数 w,m,n,w 为排号宽度,m,n 为待计算的楼号。

输出格式
输出一个整数,表示 m,n 两楼间最短移动距离。

数据范围
1≤w,m,n≤10000,

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int x1,x2,y1,y2,ans;
    int w,m,n;
    cin>>w>>m>>n;
    y1=ceil(float(m)/float(w)*1.0);  //必须先转化为float类型 
    if(y1%2!=0)
    {
        if(m%w!=0)
            x1=m%w;
        else
            x1=w;
    }
    else
    {
        if(m%w!=0)
            x1=w+1-m%w;
        else
            x1=1;
    }
    y2=ceil(float(n)/float(w)*1.0);;
    if(y2%2!=0)
    {
        if(n%w!=0)
            x2=n%w;
        else
            x2=w;
    }
    else
    {
        if(n%w!=0)
            x2=w+1-n%w;
        else
            x2=1;
    }
    ans=abs(x1-x2)+abs(y1-y2);
    //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2;
    cout<<ans;
    return 0;

 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
1个月前

题目描述

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料,凭3个瓶盖可以再换一瓶C型饮料,并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下,如果小明不浪费瓶盖,尽量地参加活动,那么,对于他初始买入的 n 瓶饮料,最后他一共能喝到多少瓶饮料。

输入格式
输入一个整数 n,表示初始买入的饮料数量。

输出格式
输出一个整数,表示一共能够喝到的饮料数量。

数据范围
0<n<10000

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int ans=0,m=0;
int sum(int n)
{
        m++;
    if(n>=3)
    {
        if(m==1)
            ans+=(n+n/3);
        else
            ans+=(n/3);
        n=(n/3+n%3);
        sum(n);
    }
    else
        return ans;
}
int main()
{
    int n;
    cin>>n;
    if(n<3)
    {
        cout<<n;
    return 0;
    }   
    sum(n);
    cout<<ans;
    return 0;
}




自律
1个月前

题目描述

长 100 厘米的细长直杆子上有 n 只蚂蚁。

它们的头有的朝左,有的朝右。

每只蚂蚁都只能沿着杆子向前爬,速度是 1 厘米/秒。

当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。

这些蚂蚁中,有 1 只蚂蚁感冒了。

并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。

请你计算,当所有蚂蚁都爬离杆子时,有多少只蚂蚁患上了感冒。

输入格式
第一行输入一个整数 n, 表示蚂蚁的总数。

接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。

正值表示头朝右,负值表示头朝左,数据中不会出现 0 值,也不会出现两只蚂蚁占用同一位置。

其中,第一个数据代表的蚂蚁感冒了。

输出格式
输出1个整数,表示最后感冒蚂蚁的数目。

数据范围
1<n<50,
0<|Xi|<100

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

首先以感冒的蚂蚁为中心,碰头之后回头和不回头其实是一样的,因为两个蚂蚁同样都感冒了,所以碰头可以看作穿过。
模拟情景:首先将碰头的概念换成穿过,先将所有数字按绝对值大小排序,你会发现中心感冒蚂蚁左边只有向右走的蚂蚁有效,向左走的蚂蚁只能穿过向右的未感冒的蚂蚁直到走出范围,同样右边的蚂蚁只有向左走的有效。然后统计中心蚂蚁左边的正数和右边的负数即可,然后有一种特殊情况如果中心蚂蚁向左走,其左边没有蚂蚁向右走,或者中心蚂蚁向右走,右边没有蚂蚁向左走时,由于速度相同,除中心蚂蚁外,任何蚂蚁都不会感冒。这种情况用if判断一下即可。

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<math.h> 
using namespace std;
int main()
{
    int a[100],i,j,n,m,first,local,ans=1,sum1=0,sum2=0;
    a[100]={0};
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        first=a[0];  //记录中心蚂蚁 
    }
    for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(sqrt(a[j]*a[j])>sqrt(a[j+1]*a[j+1]))  //按绝对值大小排序 
            {
                m=a[j];a[j]=a[j+1];a[j+1]=m;
            }
        //for(i=0;i<n;i++)
        //cout<<a[i]<<" ";
    for(i=0;i<n;i++)
        if(a[i]==first)
            local=i;          //找出中心蚂蚁位置 

    for(i=0;i<local;i++)
        if(a[i]>0)
        {
            sum1++;         //判断其左边是否有向右走的蚂蚁 
            ans++;
        }

    for(i=local+1;i<n;i++)
        if(a[i]<0)
        {
            sum2++;         //判断其右边是否有向左走的蚂蚁 
            ans++;
        }
    if(sum1==0||sum2==0)
        ans=1;

    cout<<ans;
    return 0;

 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



自律
1个月前




自律
1个月前

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题:

在 1∼N 的某个排列中有多少个连号区间呢?

这里所说的连号区间的定义是:

如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。

当 N 很小的时候,小明可以很快地算出答案,但是当 N 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式
第一行是一个正整数 N,表示排列的规模。

第二行是 N 个不同的数字 Pi,表示这 N 个数字的某一排列。

输出格式
输出一个整数,表示不同连号区间的数目。

数据范围
1≤N≤10000,
1≤Pi≤N

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

经参考题解后小结
一、由题目知N个数字一定是1~N且不重复出现
二、本题有一个规律,如果在一个区间满足最大值减最小值等于他们相差的位数((max-min)==(j-i))的时候可以满足题目要求,这道题目就不难解决了。

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
int main()
{
    int a[10001],n,i,j,k=0,max,min;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        max=0;
        min=10000;      //扫出i j之间的最大最小值 
        for(j=i;j<n;j++)
        {
            if(a[j]>max)
                max=a[j];
            if(a[j]<min)
                min=a[j];

            if(max-min==j-i)
            k++;
        }
    }
    cout<<k;
} 



自律
1个月前