蓝蓝算法题（一）

讲在前面：1.本人正在逐步学习C++，代码中难免有C和C++（向下兼容）混用情况。2.算法题目来自蓝蓝知识星球，没有对应的判决系统，运行到判决系统可以会有部分案例不能通过。

求素数

暴力求解（1 - n试探）

#include <iostream> 
using namespace std;
int main(){int num, i;cin >> num ;for(i = 2; i < num ;i ++){if ( num % i == 0) {cout << "不是素数" << endl;break;} }if ( i == num ) cout << "是素数" << endl;return 0;
}

优化算法——奇数优化（由于所有素数除了2，都是从奇数中出现。所以我们可以先去掉偶数，再筛选，这样的效率就会更高一点）
一个数如果不是素数则有两种情况：1.是偶数 2.可以被[3,n-1]之内的某些奇数整除

//求素数
#include <iostream> 
using namespace std;
int main(){int num, i, flag = 1;cin >> num ;if ( num % 2 == 0) flag = 0; //不是素数 for(i = 3; i < num ;i += 2 ){if ( num % i == 0) {flag = 0;break;} }if ( flag == 1 ) cout << "是素数" << endl;else cout << "不是素数" << endl;return 0;
}

优化算法——平方根优化
每一个数的因数都是成对出现的 且以其平方根为分界线。例如：30 （1,30），（2,15），（3,10），（5,6）以sqrt(30)为分界线。

//求素数
#include <iostream> 
#include <cmath>
using namespace std;
int main(){int num, i;cin >> num ;for(i = 2; i < (int) sqrt( num ) + 1 ;i ++){if ( num % i == 0) {cout << "不是素数" << endl;break;} }if ( i == num ) cout << "是素数" << endl;return 0;
}

求完全数

暴力求解

//求完全数 
#include <iostream> 
#include <cmath>
using namespace std;
bool perfect( int num );
int main(){int num, i;cin >> num ;for(i = 2; i <= num ;i ++){if ( perfect( i ) )  cout << i << endl;}return 0;
}
bool perfect( int num ){int sum = 1;for ( int i = 2; i < num; i ++){if ( num % i == 0 ) sum += i; }if ( sum == num ) return true;return false;
}

优化：利用欧拉公式求完全数

//求完全数
#include <iostream> 
#include <cmath>
using namespace std;
bool is_prime( int num ); //求素数部分 可以参照题目一的多种方法
int main(){int num,ans = 0;cin >> num;for(int i = 2; i <= num && pow(2, i - 1) * (pow(2 , i)-1) <= num; i++)){if ( is_prime( i ) && is_prime( pow(2,i)-1)) ans ++;}cout << ans << endl;
}
bool is_prime( int num ){int i = 2;for( ; i < (int) sqrt( num ) + 1 ;i ++){if ( num % i == 0) return false;	}if ( i == num ) return true;
} 

统计字符串字符

给定字符串ASCII码是【1,127】，统计其中不同字符个数。例如：aaabbbc 输出3

利用桶的思想：
开辟一个大小为 128 的数组初始化全为0，若有对应字母出现则在桶序数上+1，最后统计不为0的个数就是不同的字母个数。

#include <iostream> 
#include <string>
using namespace std;
int main(){string str;int cnt[128] = {0}, ans = 0;cin >> str;for(int i = 0; i < str.length() ; i++){cnt[ (int) str[i]] += 1;}for(int i = 0; i < 128 ; i++){if ( cnt[i] != 0)  ans++;}cout << ans << endl;
}

求最大公约数和最小公倍数

两个数A B的minmultiple（最小公倍数）* maxdivisor（最大公约数） = A * B
两个数最大公约数三种计算方法

#include <iostream> 
#include <algorithm>
using namespace std;
//采用辗转相除法（欧几里得）
int GetMaxDivisor(int a,int b){if(b == 0)return a;return GetMaxDivisor(b, a%b);
}int main()
{int a, b;cin >> a >> b;int md = GetMaxDivisor(a,b);int mm = a * b / md;cout << "最大公约数:" << md << "   最小公倍数:" << mm;return 0;
}

小球运动

小球从指定高度落下，每次弹起高度减半，问小球从落下到静止经过的距离（float h < 10^-6|| double h<10^-15认为弹起高度为0 达到静止）

#include <iostream> 
using namespace std;
int main()
{double height, sum ;cin >> height;// 从上向下 初始距离height sum = height;while( height ){// 从弹起到落下经过的距离是 弹起高度的2倍 即是上次弹起的高度值 sum += height;height /= 2;}cout << sum << endl;return 0;
}

答案正确

得到“答案正确”的条件是：

1.字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2.任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
分析

1.字符串中必须有’P’,‘T’,‘A’；
2.‘P’必须在‘T’之前，A穿插其中；
3.P前面的A的个数 乘以 P和T之间的A的个数 等于 T后面的A的个数——成立条件2中 可以推出

#include <iostream> 
#include <string>
using namespace std;
int main(){string str;int num = 0;cin >> num;while(num){cin >> str;int num1 = 0, num2 = 0, num3 = 0;int j = 0, k = 0;for(int i = 0; i < str.length(); i++){if( str[i] == 'P'){j = i; break;}else if( str[i] == 'A' ) num1 += 1;}for(j+1 ; j < str.length(); j++){if( str[j] == 'T'){k = j; break;}else if( str[j] == 'A') num2 += 1;}for(k+1 ; k < str.length(); k++){if( str[k] == 'A' ) num3 += 1;}if( num1 * num2 == num3 && (num1 + num2 + num3 + 2) == str.length() && str.length() > 2) cout << "YES" << endl;else cout << "NO" << endl;num --;}return 0;
}

计算字符个数

由于主串和目标字符都会有大小写的情况出现，所以代码中一致转换为小写。

#include <iostream> 
#include <string>
#include <algorithm>
using namespace std;
int main(){string str; char ch;int ans=0;cin >> str >> ch;//调用算法库中函数将 str全部转换为小写字母 transform(str.begin(),str.end(),str.begin(),::tolower);//将目标字母转换为小写  toupper()转换为大写 ch = tolower(ch); for( int i = 0; i < str.length(); i++){if( str[i] == ch) ans++;}cout << ans << endl;
}

字符串反转

利用第三个变量实现两个字符的调换

#include <iostream> 
#include <string>
using namespace std;
int main(){string str;cin >> str;char ch;//范围是长度的一半，否则两次调换是使得结果与原来相同for(int i = 0; i < str.length()/2 ; i++){//体会双指针的思想ch = str[i];str[i] = str[str.length()-i-1];str[str.length()-i-1] = ch;} cout << str << endl;
}

兔子数量

斐波那契数列
递归调用时要注意递归出口！

#include <iostream> 
#include <string>
using namespace std;
int Fibonacci( int num);
int main(){int num,cnt = 0;cin >> num;cnt = Fibonacci(num);cout << cnt << endl;return 0;
}
int Fibonacci(int num){//递归出口if(num == 1|| num == 2) return 1;return Fibonacci(num-2) + Fibonacci( num-1);
}

迭代
迭代求斐波那契数列

成绩转换

将百分制成绩转换为等级制成绩。利用 if -else 即可

鸡兔同笼

解方程问题
注意判断数据的合理性

#include <iostream> 
using namespace std;
int main(){int heads, legs;cin >> heads >> legs;int rabbits = legs/2 - heads, chickens = 2 * heads - legs/2;if(rabbits * 4 + chickens * 2 == legs) cout << "兔子有" << rabbits << "只，鸡有" << chickens <<"只" << endl;else cout << "No answer" << endl;return 0;
}