记录自己为学习算法而入门c++的学习历程,并随时在手机上看自己写的狗屎代码.

想到可以优化的地方修改,有更好的方法另加.

题目,算法均来源于网络查找.本文仅作个人学习使用,不保证严谨度.

运行程序Techie Delight

统计字符1

不等同于字符串,统计的对象是从1到n特定数字出现的次数.当时写的时候一直想着将这n个数存到数组中再操作,但对如何处理毫无办法.

#include <iostream>
using namespace std;
int main(){
    int n,x,num,count=0;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        num=i;
        while(num!=0){//狠狠提取数字,与x比较
            if(num%10==x) count++;
            num/=10;
        }
    }
    cout<<count;
    return 0;
    }

求最大公约数

最大公约数 - OI Wiki

欧几里得算法(辗转相除法)

数学原理:两个整数的最大公约数等于其中较小的那个数和两数相除所得余数的最大公约数。

GCD(a,b) = GCD(b,a%b)

//递归实现
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

//迭代法
int gcd(int a,int b){
	while(b!=0){
		int temp=a;
		a=b;
		b=temp%b;
	}
	return a;
}

  • 试着用以上方法求斐波那契数列相邻两项的最大公因数?效率会大打折扣.

判断:一个数及它的各个位是否都是质数

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

 bool prime(int n){
     //小于4时特判
     if(n==1) return false;
     if(n==2||n==3) return true;
     for(int i=2;i<sqrt(n)+1;i++){
         //出现一次整除结束
         if (n%i!=0) continue;
         if(n%i==0) return false;
     }
     return true;
 }

bool every_num(int n){//判断每一位数字
    while(n!=0){
        if(!prime(n%10)) return false;
        n/=10;
    }
    return true;
}

int main(){
    int t;
    int num[1000];
    cin>>t;
    for(int i=1;i<=t;i++) cin>>num[i];
    for(int j=1;j<=t;j++){
        if(prime(num[j])&&every_num(num[j]))
            cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
    return 0;
}
  • 判断代码另写函数方便多次调用.