基础算法题

本文主要是介绍基础算法题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Problem

3或5的倍数

2:偶斐波那契数

4:最大回文乘积

5 窗口移动

11:方向数组

13大整数加法 、

14最长考拉兹序列

15：网格路径

25:1000位斐波那契数

1:3或5的倍数

在小于10的自然数中，3或5的倍数有3、5、6和9，这些数之和是23。

求小于1000的自然数中所有3或5的倍数之和。

考查倍数（）% 取模运算符，整除后的余数 ,整除则为倍数

  1 #include<iostream>
  2 using namespace std;
  6 int main(){
  7     int ans=0;                                                                                                                                                                                                 8     for(int i =1;i<1000;i++){
  9         if(i%3==0||i%5==0){
 10             ans+=i;
 11         }
 12     }
 13    cout << ans << endl;
 14     return 0;
 15 }

等差数列 优化重复标记

 #include<iostream>
  2 using namespace std;
  3 首项加末项 * （sum / 首选)   /2
  4 int main (){
  5     int sum3 =(3+999)*333/2;
  6     int sum5 =(5+995)*199/2;
  7     int sum15=(15+990)*66/2;
  8
  9     int reult = sum3 + sum5 -sum15;
 10     cout << reult << endl;
 11
 12     return  0;                                                                                                       13 }

2:偶斐波那契数

斐波那契数列中的每一项都是前两项的和。由1和2开始生成的斐波那契数列的前10项为：

1,2,3,5,8,13,21,34,55,89,…

考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。

  1 #include<iostream>
  2 using namespace std;
  3
  4 int main(){
  5     long long temp=0;
  6     int a=1;
  7     int b=2;
  8     while(b<4000000){
  9         if(b %2==0 ) {
 10             temp +=b;
 11         }
 12         b=a+b;
 13         a=b-a;                                                                                                                                14     }
 15     cout  << temp << endl;
 16     return  0;
 17 }

4:最大回文乘积

回文数就是从前往后读和从后往前读都一样的数。由两个2位数相乘得到的最大的回文数是 9009=91×99。

求由两个3位数相乘得到的最大的回文数。

最重要的反转数字 取模可以理解为lsat的数字

主方法这 公式 临时数据 =t * 10 + {x} %* 10

x/=10; 是为了last 的位子往前移

  1 #include<iostream>
  2 using namespace std;
  3
  4
  5 int func(int x){
  6    int raw =x ,t=0;
  7    while(x){
  8      t= t * 10+ x % 10;
  9      x=x/10;
 10    }
 11  int reulte =raw==t;
 12  return reulte;
 13 }
 14
 15
 16
 17 int main(){
 18     int temp=0;
 19     for(int i=100; i<1000;i++){                                                                                      20         for(int j=i;j<1000;j++){
 21           if(func(i*j))
 22           {
 23              temp=max(temp,i*j);
 24           }
 25       }
 26     }
 27     cout << temp << endl;
 28     return 0;
 29 }
 30

5 窗口移动

  1 #include<iostream>
  2 using namespace std;
  3
  4 char str[1005];
  5 int main(){
  6     long long ans =0, now =1 ,count_cnt=0;
  7      cin >> str;
  8      for(int i=0;i<str[i];i++){
  9          if(i<13){
 10             //now windowns
 11             now*=str[i]-'0';
 12          } else if(str[i]!='0')
 13          {
 14             now*=str[i]-'0';
 15          }else{
 16             count_cnt++;
 17          }
 18
 19          if(i>=13){
 20             //则窗体向后走
 21              if(str[i-13]!='0'){
 22                  now /=str[i-13]-'0';
 23              }
 24              else{
 25                  count_cnt--;
 26              }
 27          }
 28          if(count_cnt ==0){                                                                                                                                                                                   29              ans=max(ans,now);
 30          }
 31      }
 32     cout << ans <<endl;
 33     return 0;
 34 }

11:方向数组

<重定向符

  1 #include<iostream>
  2 using namespace std;
  3
  4
  5 int num[30][30] ,ans;
  6 int dirx[4]={-1,0,1,1};/*定义方向数组*/
  7 int diry[4]={1,1,1,0};
  8
  9 int main(){
 10     for(int i=5;i<25;i++){
 11         for(int j=5;j<25;j++){                                                                                                                                                                                12             cin >> num[i][j];
 13         }
 14     }
 15
 16     for(int i=1;i<25;i++){  //x 行
 17       for(int j=1;j<25;j++){  // y 列
 18           for(int k=0;k<4;k++){  //方向
 19               int t=num[i][j];
 20               for(int l=1;l<4;l++){ //除了自己的走三步数
 21                     //新坐标
 22                     int x= i+l * dirx[k];
 23                     int y= j+l * diry[k]; //l倍的纵坐标
 24                     t *=num[x][y];//这个格子的值x到方向的答案中
 25               }
 26               ans=max(ans,t); //尝试更新答案  求玩一次答案则更新一次答案
 27           }
 28        }
 29     }
 30
 31     cout<< ans <<endl;
 32     return 0;
 33 }

13大整数加法

step1: 长度大于int 64的数字加法一般有另外的处理方法

通过两个字符数组存 转为数值数据 进行计算

先把输入的数字长度 存在下标为0 的位子 .

step2:通过num数组来存字符数组的值(经数组反过来存)

step3:通过取出最大的数组位数

作为sum数组长度， 则将sum数组num1[i]+num2[i];

step4: 已经 拿到了加数值了 //则进位

如果下表位数大于9则是需要进位的

公式为：sum[i+1]=sum[i+1]+sum[i]/10;

          sum[i]%=10;

刚刚定义的下标长度0 用于判断最高位是否有进位如果则最高位长度也随之发生变化

最后倒叙输出sum数组即可

#include <iostream>
#include <cstring>
using namespace std;

char s1[1005],s2[1005];
int num1[1005],num2[1005],sum[1005];
int main(){
    cin>> s1>> s2;
    num1[0]=strlen(s1);
    num2[0]=strlen(s2);
    
    //数字数组的下表 j；
    for(int i=0,j=num1[0];s1[i];i++,j--){
        num1[j]=s1[i]-'0';  //必须减去0才能获得字符的值
    }

    for(int i=0,j=num2[0];s2[i];i++,j--){
        num2[j]=s2[i]-'0';
    }
    
    sum[0]=max(num1[0],num2[0]);
    for(int i=1;i<=sum[0];i++){
        sum[i]=num1[i]+num2[i];
    }
        
    //进位
    for(int i=1;i<=sum[0];i++){
        cout<< sum[i] <<endl;
        if(sum[i]>9){
            sum[i+1]+=sum[i]/10;
            sum[i]%=10;
            if(i==sum[0]){
                sum[0]++;
            }
        }
    }

    //倒着输出
    for(int i=sum[0];i>0;i--){
        cout<< sum[i];
    }
    cout << endl;
    return 0;
}

cout<< sum[i] <<endl;

14最长考拉兹序列

考了在定义在正证书及上迭代的规则

n → n/2 (n is even) 如果为偶数 n → 3n + 1 (n is odd) 若n为奇数

从13开始，可以迭代生成的序列

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

在小于100万的数中 开始迭代的生成的序列最长 递归 递归

#include<iostream>
using namespace std;

long long  num[10000005];
 long long func(long long x){
        if(x==1){
            return 1;
        }
        if(x<10000000&&num[x]!=0){
              return num[x]; 
        }
        long long t;
        if(x%2 == 0){
          t= func(x/2)+1;
        }else{
            t=func(3* x +1)+1;
        }
        if(x<10000000){
            num[x]=t;
        }
        return t;
   }


int main(){
   long long ans=0 ,mmax=0;
   for(int i=1;i<=10000000;i++){
   long long  t =func(i);
   if(t>mmax){
     mmax =t;
     ans=i;
   }

  }
  cout<< ans <<endl;
return 0;
}

组和排列 我反正看不懂

#include <iostream>
using   namespace std;

long long ans[25][25];
int main()
{
  long long fin = 1;
  for (int i = 40, j = 1; i > 20; i--, j++)
  {
    fin*=i;
    fin/=j;
  }

  cout << fin << endl;
  return 0;
}

15：网格路径

从一个2×2网格的左上角出发，若只允许向右或向下移动，则恰好有6条抵达右下角的路径。

动态规划的问题:

递推公式为：

你不能让他从0开始必须从第一位开始算，因为外面是一层保护0

由公式→dp[x[[y]=dp[x-1][y]-dp[x][y-1];

#include <iostream>
using   namespace std;

long long ans[25][25];
int main()
{
  for (int i = 1; i <= 21; i++)
  {
    for (int j = 1; j <= 21; j++)
    {
      if (i == 1 && j == 1) {
        ans[i][j] = 1;
        continue;
      }
      ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
    }
  }
  cout << ans[21][21] << endl;

  return 0;
}

—2:组和排序

25:1000位斐波那契数

ps：实际应该为两个数组辗转相加 ，由于是两个数组来回相加

   #include<iostream>
  2 using namespace std;
  3 void func(int *n1, int *n2){
  4     //n2可能比N1短先更新长度
  5    n2[0]=n1[0]; //更新长度 先给数字的长度
  6    for(int i=1;i<=n2[0];i++){
  7        n2[i]+=n1[i];
  8        if(n2[i]>9){
  9            n2[i+1]+=n2[i]/10;
 10            n2[i]%=10;
 11            if(i==n2[0]){
 12                //最高位变化
 13                 n2[0]++;
 14            }
 15        }
 16    }
 17 }
 18 int main(){
 19    int num[2][1111]={{1,1},{1,1}},a=1,b=1;
 20        for(int i=3;1;i++){
 21        //这个一直会计算下去 1 为真
 22        //两个数组相加
 23            func(num[a],num[b]);
 24            if(num[b][0]>=1000){
 25               cout<< i <<endl;
 26        //这是项数
 27               break;
 28            }
 29            //如果没有就交换值接着+
 30             swap(a,b);
 31           }
 32
 33     return 0;
 34 }

26大整数乘法—高精度

1 存（和加法一致）（数字第一位存长度） 2 算 3进位

某两个数相乘为 min x+y-1 | max x+y

核心的公式为 n=x+y-1 ;

取乘积最小的位数 如果高位则在高位判断进位即可

   #include<iostream>
  2 #include<cstring>
  3 using namespace std;
  4
  5 char s1[1005],s2[1005];
  6 int n1[1005],n2[1005],ans[2005];
  7 int main(){
  8     cin>> s1 >> s2;
  9     n1[0]=strlen(s1),n2[0]=strlen(s2);
 10     for(int i=0,j=n1[0];i<n1[0];i++,j--){
 11          n1[j]=s1[i]-'0';
 12     }
 13     for(int i=0,j=n2[0];i<n2[0];i++,j--){
 14          n2[j]=s2[i]-'0';
 15     }
 16     ans[0]=n1[0]+n2[0]-1;
 17     for(int i=1;i<=n1[0];i++){
 18         for(int j=1;j<=n2[0];j++){
 19             ans[i+j-1]+= n1[i] * n2[j];
 20         }
 21     }
 22     for(int i=1;i<=ans[0];i++){
 23         if(ans[i]>9){
 24             ans[i+1]+=ans[i]/10;
 25             ans[i]%=10;
 26             if(ans[0]==i){
 27                ans[0]++;
 28             }
 29         }else if(i==ans[0] && ans[i+1]!=0){
 30             ans[0]++;
 31         }
 32     }
 33     for(int i =ans[0];i>0;i--){
 34         cout << ans[i];   
 35     }                                                                                                                                              35     }
 36     cout<< endl;
 37     return 0;
 38 }

ps :99x99乘出的为4位, 得到一个四位数 , 由于你是四位数

在存储上你必然由一个三位数进位而来，(因为要考虑高位不进位的场景) 所以用x+y - 1

这篇关于基础算法题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！