锐客网

  1. 首页 > it技术 > >

【算法笔记入门篇】

第四章 二分法

  1. 在有序的序列中查找X;
  2. 求解序列中第一个大于等于x元素的位置
  3. 查找第一个大于x元素的位置
#include #include #include using namespace std; /*查找x*/ int searchX(int data[],int left, int right, int x){ int mid; while(left<=right){ mid = (left + right)>>1; if(data[mid] == x) return mid; else if(data[mid] > x) right = mid + 1; else left = mid; } return -1; } /* 求解序列中第一个大于等于x元素的位置 */ int solve(int data[],int left,int right, int x){ int mid; while(left < right){ //推出循环的时候left == right mid = (left + right)>>1; if(data[mid] >= x){ right = mid; }else { left = mid + 1; } } return left; } /*查找第一个大于x元素的位置*/ int solve2(int data[],int left, int right, int x){ int mid; while(left < right){ mid = (left + right)>>1; if(data[mid] > x) right = mid; else left = mid + 1; } return left; } const int n = 10; int main(){ int A[n] = {1,3,4,6,7,8,10,11,12,15}; int posX = searchX(A,0,n-1,10); if(posX != -1){ printf("%d-%d\n",posX,A[posX]); }else{ printf("cannot find x\n"); } int index = solve(A,0,n-1,9); printf("%d-%d\n",index,A[index]); index = solve2(A,0,n-1,6); printf("%d-%d\n",index,A[index]); return 0; }

快速幂 【【算法笔记入门篇】】两种方法，其中迭代方法中采用分解的思路
比如求解2^13= 2^8 * 2^4 * 2^1;
#include #include #include using namespace std; typedef long long LL; /* 求解快速幂 a^b%m; */ //迭代方法求解 LL binarypow(LL a,LL b,LL m){ LL ans = 1; while(b > 0){ if(b & 1){ ans = ans * a % m; } a = a*a % m; b>>=1; } return ans; } //递归方法 LL recursionpow(LL a,LL b, LL m){ if(b == 0) return 1; if(b & 1) return a*recursionpow(a,b-1,m) % m; else{ LL mul = recursionpow(a,b>>1,m); //减少计算量 return mul*mul%m; } } int main(){ LL ans = binarypow(2,10,100000); printf("%lld\n",ans); ans = recursionpow(2,10,100000); printf("%lld",ans); return 0; }

第五章数学问题（大整数+素数筛+分数问题） 大整数问题 在写一些编程的题目时候遇到的大整数问题，可以在c++语言做出如下定义并使用。java中有BigDecimal这个类，而在c++只能自己写一个基本的数据结构数组来保存数据。
代码如下：
#include #include #include using namespace std; /* 3 2 1 -1 2 3 -------*/ struct bign{ int d[1000]; int len; bign(){ memset(d,0,sizeof(d)); //初始化数组 len = 0; } }; bign change(string s) { bign c; c.len = s.length(); for(int i = 0; i < s.length(); i++){ c.d[i] = s[s.length()-i-1]-'0'; } return c; } void printfArra(int d[],int len){ for(int i = 0; i < len; i++){ printf("%d",d[i]); } printf("\n"); } //高精度加法 bign add(bign a, bign b){ bign c; int cx = 0; for(int i = 0; i=1 && c.d[c.len-1] == 0) { c.len--; } return c; } //大整数的乘法 一个整数*大整数 a*b bign multiple(bign a, int b){ bign c; int carry = 0; for(int i = 0; i < a.len; i++){ int temp = a.d[i] * b + carry; c.d[c.len++] = temp % 10; carry = temp / 10; } while(carry){ c.d[c.len++] = carry % 10; carry /= 10; } return c; } bign divide(bign a, int b, int &r){ //大整数除法 a/b 余数=r bign c; c.len = a.len; for(int i = c.len-1; i >= 0; i--){ r = r*10 + a.d[i]; if(r < b) c.d[i] = 0; else { c.d[i] = r / b; r = r % b; } } while(c.len - 1>=1 && c.d[c.len-1]==0){//去除最高位是0的情况 c.len--; } return c; } void print(bign c){ for(int i = c.len-1; i >= 0; i--){ cout<>a>>b; //输入两个数 bign n1 = change(a); bign n2 = change(b); bign c = add(n1,n2); print(c); *//* string a,b; cin>>a>>b; //输入两个数 if(a.compare(b) < 0){ //如果字符串b>a则 做减法的时候要交换a,b，同时输出符号 swap(a,b); cout<<"-"; } bign c = devide(n1,n2); print(c); //打印相加结果 */ /* //大整数的乘法 string a; int b; cin>>a>>b; bign n1 = change(a); bign c = multiple(n1,b) ; print(c); */ // 大整数除法 string a; int b; int r = 0; cin>>a>>b; bign n1 = change(a); bignc = divide(n1,b,r); print(c); printf("\nr=%d:",r); //余数 }

素数问题 经常遇到素数相关问题，有两种方法。前面的博客我也写过，今天在重新review一下。
#include #include #include #include using namespace std; /* 方法1. 使用常规方法 n%i(i>=2 && i <= sqrt(n) ) 方法2.使用素数筛法求解2-n范围内的素数 */ bool flag[1000]; //声明一个标记数组 素数筛法就是以空间换时间的列子 int prime[1000]; int index = 0; //T1求解n以内的素数 void sovlePrime(int n){ memset(flag,true,sizeof(flag)); for(int i = 2; i <= n; i++) { if(flag[i]){ prime[index++] = i; for(int j = i; j <= n; j+=i){ flag[j] = false; } } } } //T2求解质因子分解 struct Data{ int a,b; //a是底数 b是指数 }; void devideeNum(int n) { //将n分解成质数 如180=2^2*3^2*5; sovlePrime(n); //先求解质数 Data row[10]; int c = 0; cout< 0){ cout<<"*"; } cout<

求最大公约数和最小公倍数 求解最大的公约数和最小公倍数代码，以及在次基础之上来求解分数的代码如下：
#include #include #include using namespace std; //算法笔记第五章 //求最大公约数3 63 //若a>bgcd(a,b)=gcd(b,a%b); gcd(a,0) = a; //推理 r=a-b*k; 假设d是a,b的最大公约数。则d也是r的公约数 //r=a%b; 得 d是b和a%b的最大公约数 //这种方法用的是欧几里得辗转相除法 int gcd(int a, int b) { if(b == 0) return a; else return gcd(b,a%b); }//求最小公倍数ab/d,就是两个数的乘积/最大公约数 int lcm(int a, int b) { return a/gcd(a,b)*b; } //5.3分数的四则运算 //分数表示 分子和分母 struct Fraction{ int up,down; //up分子 down分母 }; //1.分数的化简 //down为非负数，若分数为负的，则让分子up 为负的 //如够分数恰为0 ，规定分子为0 分母为1 //分子分母没有除1以外的公约数 Fraction reduction(Fraction res) { if(res.down < 0){ res.up = -res.up; res.down = -res.down; } if(res.up == 0){ res.down =1; }else{ int d = gcd(abs(res.up),abs(res.down)); res.up /= d; res.down /= d; } return res; } //分数的加法 Fraction addF(Fraction a, Fraction b) { Fraction c; c.up = a.up*b.down + b.up*a.down; c.down = a.down*b.down; return reduction(c); } //分数的减法 Fraction deviceF(Fraction a, Fraction b) { Fraction c; c.up = a.up*b.down - b.up*a.down; c.down = a.down*b.down; return reduction(c); } //分数的乘法 Fraction multiF(Fraction a, Fraction b) { Fraction c; c.up = a.up*b.up; c.down = a.down*b.down; return reduction(c); } //分数的除法 Fraction devideF(Fraction a, Fraction b) { Fraction c; c.up = a.up * b.down; c.down = a.down*b.up; return reduction(c); } int main(){ //求最小公倍数测试 //初始条件a>b // int ans = lcm(9,3); // printf("%d",ans); // 分数的加法测试 /* Fraction a; a.down = -4; a.up = 4; Fraction b = reduction(a); printf("%d/%d",b.up,b.down); */ Fraction a,b; a.up = 9; a.down = -4; b.up = 4; b.down = 2; Fraction c = addF(a,b); printf("%d/%d",c.up,c.down); return 0; }

【注】这是我在准备考研复试时候，看《算法笔记》胡凡的书练习的代码，只想加深一下印象，因此把自己的东西输出一下。如有错误还请指之处，万分感谢！！！

    推荐阅读


    上一篇：【王小二环游中国旅行日记连载】恩，买了包卫生巾

    下一篇：Android 应用更新使用Bugly