关于C++的几个经典案例代码
大数减法问题
因为较大整数的相加很可能超出整型的32位限制,或者本身就是超出限制的大数之间的加减运算。
所以我们需要单独写一个能大数相加减的函数
基本原理:把数字用字符串的形式来保存加减的结果或大数字本身就不会超出限制,比如“999999999999999999999999999999” 多长都可以。
#include <iostream> #include <vector> #include<math.h> using namespace std; //************************大数减法****************************** bool cmp(vector<int> &A,vector<int> &B) { if(A.size()!=B.size()) { return A.size()>B.size(); } for(int i = A.size(); i>=0; i--) //A,B长度相同 { if(A[i]!=B[i]) { return A[i]>B[i]; } } return true; } vector<int> sub(vector<int> &A,vector<int> &B) //C=A-B { int t = 0;//借位 vector<int> C; for(int i = 0; i<A.size(); i++) { t = A[i]-t; if(i<B.size()) { t-=B[i]; } C.push_back((t+10)%10); if(t<0) { t = 1; } else { t = 0; } } while(C.size()>1&&C.back()==0) //去除多余前导0 { C.pop_back(); //同时要注意A-B=0时不能把去除掉 } return C; } void subRun() //求A-B { string a,b; vector<int> A,B,C; cin>>a>>b; for(int i = a.size()-1; i>=0; i--) { A.push_back(a[i]-'0');//记得转为数字 } for(int i = b.size()-1; i>=0; i--) { B.push_back(b[i]-'0'); } if(cmp(A,B)) //A>=B { C = sub(A,B); for(int i = C.size()-1; i>=0; i--) { cout<<C[i]; } } else //A<B { C = sub(B,A); cout<<"-"; for(int i = C.size()-1; i>=0; i--) { cout<<C[i]; } } }
绘制余弦曲线
余弦函数曲线 分析:输出余弦曲线,余弦曲线坐标显示分为x轴和y轴 即一个x对应一个y值,且余弦函数的是关于π对称的,需要注意的是cos()函数使用的是 弧度.acos函数是反余弦函数。本例基于acos绘制余弦函数。
//************************绘制余弦曲线****************************** void drawCos() { double y; int x,m; for(y=1; y>=-1; y-=0.1) /*y为列方向,值从1到-1,步长为0.1*/ { m=acos(y)*10; /*计算出y对应的弧度m,乘以10为图形放大倍数*/ for(x=1; x<m; x++) printf(" "); printf("*"); /*控制打印左侧的 * 号*/ for(; x<62-m; x++)printf(" "); printf("*\n"); /*控制打印同一行中对称的右侧*号*/ } }
兔子数量问题
有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少?
/* 有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少? */ void numRabbit() { // 月份 int month = 0; while(cin >> month) { // 分别是三个月份大的兔子数量 int m1 = 1, m2 = 0, m3 = 0; while(--month) { // 三个月大的兔子等于原来的加上两个月大的 m3 = m3 + m2; // 两个月大的由一个月份大的提供 m2 = m1; // 每月会生产新兔子 m1 = m3; } // 三个加起来 cout << m1 + m2 + m3 << endl; } }
快速排序问题
快速排序(Quicksort),计算机科学词汇,适用领域Pascal,c++等语言,是对冒泡排序算法的一种改进。
速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
关键点
将第一个元素放到中间的位置,使得左边都小于它,右边都大于它
第一个元素的左边和右边,按照步骤一递归
//***********************************快速排序**************************************************** void quickSort(int arr[], int begin, int end) { if (begin >= end) return; int left = begin; int right = end; int temp = arr[left]; while (left < right) { //从后往前找比他小的放前面,从前往后找比它大的放后面 //以第一个数为基准,必须先从后往前走,再从前往后走 while (left < right && arr[right] >= temp) { right--; } //跳出此循环,代表right找到了比temp小的数字,所以此时arr[left]=arr[right] if (left < right) { arr[left] = arr[right]; } while (left < right && arr[left] <= temp) { left++; }//同理 if (left < right) { arr[right] = arr[left]; } if (left == right) { arr[left] = temp; } } quickSort(arr, begin, left - 1); quickSort(arr, left + 1, end); } void runQuickSort() { int arr[11] = { 5,6,3,2,7,8,9,1,4,0,0 }; quickSort(arr, 0, 10); for (auto x : arr) { cout << x << " "; } }
函数运行
//************************主函数****************************** int main() { //subRun(); //大数减法 drawCos(); //绘制余弦曲线 //numRabbit();//兔子的数量 runQuickSort(); // 快速排序 return 0; }
全部源码
#include <iostream> #include <vector> #include<math.h> using namespace std; //************************大数减法****************************** bool cmp(vector<int> &A,vector<int> &B) { if(A.size()!=B.size()) { return A.size()>B.size(); } for(int i = A.size(); i>=0; i--) //A,B长度相同 { if(A[i]!=B[i]) { return A[i]>B[i]; } } return true; } vector<int> sub(vector<int> &A,vector<int> &B) //C=A-B { int t = 0;//借位 vector<int> C; for(int i = 0; i<A.size(); i++) { t = A[i]-t; if(i<B.size()) { t-=B[i]; } C.push_back((t+10)%10); if(t<0) { t = 1; } else { t = 0; } } while(C.size()>1&&C.back()==0) //去除多余前导0 { C.pop_back(); //同时要注意A-B=0时不能把去除掉 } return C; } void subRun() //求A-B { string a,b; vector<int> A,B,C; cin>>a>>b; for(int i = a.size()-1; i>=0; i--) { A.push_back(a[i]-'0');//记得转为数字 } for(int i = b.size()-1; i>=0; i--) { B.push_back(b[i]-'0'); } if(cmp(A,B)) //A>=B { C = sub(A,B); for(int i = C.size()-1; i>=0; i--) { cout<<C[i]; } } else //A<B { C = sub(B,A); cout<<"-"; for(int i = C.size()-1; i>=0; i--) { cout<<C[i]; } } } //************************绘制余弦曲线****************************** void drawCos() { double y; int x,m; for(y=1; y>=-1; y-=0.1) /*y为列方向,值从1到-1,步长为0.1*/ { m=acos(y)*10; /*计算出y对应的弧度m,乘以10为图形放大倍数*/ for(x=1; x<m; x++) printf(" "); printf("*"); /*控制打印左侧的 * 号*/ for(; x<62-m; x++)printf(" "); printf("*\n"); /*控制打印同一行中对称的右侧*号*/ } } /* 有一只兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子,假如兔子都不死,问每个月的兔子总数为多少? */ void numRabbit() { // 月份 int month = 0; while(cin >> month) { // 分别是三个月份大的兔子数量 int m1 = 1, m2 = 0, m3 = 0; while(--month) { // 三个月大的兔子等于原来的加上两个月大的 m3 = m3 + m2; // 两个月大的由一个月份大的提供 m2 = m1; // 每月会生产新兔子 m1 = m3; } // 三个加起来 cout << m1 + m2 + m3 << endl; } } //***********************************快速排序**************************************************** void quickSort(int arr[], int begin, int end) { if (begin >= end) return; int left = begin; int right = end; int temp = arr[left]; while (left < right) { //从后往前找比他小的放前面,从前往后找比它大的放后面 //以第一个数为基准,必须先从后往前走,再从前往后走 while (left < right && arr[right] >= temp) { right--; } //跳出此循环,代表right找到了比temp小的数字,所以此时arr[left]=arr[right] if (left < right) { arr[left] = arr[right]; } while (left < right && arr[left] <= temp) { left++; }//同理 if (left < right) { arr[right] = arr[left]; } if (left == right) { arr[left] = temp; } } quickSort(arr, begin, left - 1); quickSort(arr, left + 1, end); } void runQuickSort() { int arr[11] = { 5,6,3,2,7,8,9,1,4,0,0 }; quickSort(arr, 0, 10); for (auto x : arr) { cout << x << " "; } } //************************主函数****************************** int main() { //subRun(); //大数减法 drawCos(); //绘制余弦曲线 //numRabbit();//兔子的数量 runQuickSort(); // 快速排序 return 0; }