实验1：递归算法
折线分割
关键在于 f(n)=f(n-1)+4*(n-1)+1
#include<iostream> using namespace std; int main(){ int num=10000; int *arr=new int[10000]; arr[0]=0; arr[1]=2; for(int i=2;i<=10000;i++){ arr[i]=arr[i-1]+4*(i-1)+1; } int n; cin>>n; while(n>0){ n--; int x; cin>>x; cout<<arr[x]<<endl; } }骨牌铺方格
f(n)=f(n-1)+f(n-2) 用c++时 需要注意 溢出 数组应该用 long long
#include<iostream> using namespace std; int main(){ int x; long long *arr=new long long[51]; arr[0]=0; arr[1]=1; arr[2]=2; for(int i=3;i<=50;i++){ arr[i]=arr[i-1]+arr[i-2]; } while(cin>>x){ cout<<arr[x]<<endl; } }排队问题
f(n)=f(n-1)+f(n-2)+f(n-4) 操~蛋的是 用cpp会溢出 需要 模拟大数运算 建议直接py
#py注意事项 for i in range(1,10) i 到不到 10 #不要忘记写最后的if import sys def main(): arr=[1,1,2,4,7] for i in range (5,1200): arr.append(arr[i-1]+arr[i-2]+arr[i-4]) for line in sys.stdin: line = line.strip() if not line: continue x=int(line) print(arr[x]) if __name__ == "__main__": main()排错问题
f(n)=(n-1)(f(n-1)+f(n-2)) 使用long long 数组
#include<iostream> using namespace std; int main(){ long long *arr=new long long[21]; arr[0]=0; arr[1]=0; arr[2]=1; arr[3]=2; for(int i=4;i<=20;i++){ arr[i]=(i-1)*(arr[i-1]+arr[i-2]); } int x; while(cin>>x){ cout<<arr[x]<<endl; } }最大字段和问题
用双指针 left=right=0 right走 当sum<0 left=right+1
#include<iostream> using namespace std; int main(){ int n; cin>>n; int put=0; while(n>0){ n--; put++; int len; cin>>len; int *arr=new int[len]; for(int i=0;i<len;i++){ cin>>arr[i]; } int max=arr[0]; int sum=0; int left=0; int right=0; int resl=0; int resr=0; while(right<len && left<len){ sum+=arr[right]; if(sum>max){ max=sum; resl=left; resr=right; } if(sum<0){ sum=0; left=right+1; } right++; } cout<<"Case "<<put<<":"<<endl; cout<<max<<" "<<resl+1<<" "<<resr+1<<endl; } }作业 渐进界+递归方程+排序
主定理
差距几何
桶排序 算出平均差距 （考虑到可能为0 手动+1 扩大桶大小 可能出现问题 但这道题可以通过😀）
然后分n-1个桶 每个桶维护 一段范围数据的最大值和最小值 最后 比较相邻非空桶最大最小值之差
int fun ( int arr[],int n ){ if(n<2) return 0; int max=arr[0]; int min=arr[0]; for(int i=0;i<n;i++){ if(arr[i]>max){ max=arr[i]; } if(arr[i]<min){ min=arr[i]; } } int aver=(max-min)/n+1; int *minArr=(int *)malloc(sizeof(int)*(n-1)); int *maxArr=(int *)malloc(sizeof(int)*(n-1)); for(int i=0;i<n-1;i++){ minArr[i]=-1; maxArr[i]=-1; } for(int i=0;i<n;i++){ int num=(arr[i]-min)/aver; if(arr[i]==max){ num=n-2; } if(minArr[num]==-1){ minArr[num]=arr[i]; }else if(minArr[num]>arr[i]){ minArr[num]=arr[i]; } if(maxArr[num]==-1){ maxArr[num]=arr[i]; }else if(maxArr[num]<arr[i]){ maxArr[num]=arr[i]; } } int res=0; int pArr=0; for(int i=0;i<n-1;i++){ if(minArr[i]!=-1){ pArr=i; break; } } for(int i=pArr+1;i<n-1;i++){ if(minArr[i]==-1){ continue; }else{ if(res<minArr[i]-maxArr[pArr]){ res=minArr[i]-maxArr[pArr]; } pArr=i; } } return res; }n以内素数个数
直接假定n范围在1e8 可以通过
#include<iostream> const int MAX=1e8; using namespace std; int main(){ bool *arr=new bool[ MAX]; for(int i=0;i< MAX;i++){ arr[i]=true; } for(int i=2;i< MAX;i++){ if(arr[i]==true){ int j=i+i; while(j< MAX){ arr[j]=false; j+=i; } } } int res=0; int x; cin>>x; for(int i=2;i<=x;i++){ if(arr[i]==true) res++; } cout<<res; }快速排序
#include<iostream> using namespace std; void swap(int &a,int &b); int pfunc(int*arr,int start,int end); void quickSort(int *arr,int start,int end,int n); int main(){ int n; while(cin>>n){ int *arr=new int[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } quickSort(arr,0,n-1,n); } } void swap(int &a,int &b){ int t=a; a=b; b=t; } int pfunc(int*arr,int start,int end){ int left=start; int right=end; int hero=arr[start]; while(left<right){ while(left<right && arr[right]>=hero){ right--; } if(left<right){ arr[left]=arr[right]; left++; } while(left<right && arr[left]<=hero){ left++; } if(left<right){ arr[right]=arr[left]; right--; } } arr[left]=hero; return left; } void quickSort(int *arr,int start,int end,int n){ if(start>=end) return; int p=pfunc(arr,start,end); for(int i=0;i<n;i++){ cout<<arr[i]; if(i!=n-1){ cout<<" "; } } cout<<endl; quickSort(arr,start,p-1,n); quickSort(arr,p+1,end,n); }二路归并排序
注意mergesort 和 merge中对数组的划分能匹配就行了
#include<iostream> using namespace std; void mergeSort(int *arr,int start,int end,int n); void merge(int* arr,int start,int end,int mid); int main(){ int n; while(cin>>n){ int *arr=new int[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } mergeSort(arr,0,n-1,n); } } void mergeSort(int *arr,int start,int end,int n){ if(start==end) return ; int mid=(start+end)/2; mergeSort(arr,start,mid,n); mergeSort(arr,mid+1,end,n); merge(arr,start,end,mid); for(int i=0;i<n;i++){ cout<<arr[i]; if(i!=n-1){ cout<<" "; } } cout<<endl; } void merge(int* arr,int start,int end,int mid){ int* tempArr=new int[end-start+1]; int i=start; int j=mid+1; int k=0; while(i<=mid && j<=end){ if(arr[i]<arr[j]){ tempArr[k]=arr[i]; i++; }else{ tempArr[k]=arr[j]; j++; } k++; } while(i<=mid){ tempArr[k]=arr[i]; i++; k++; } while(j<=end){ tempArr[k]=arr[j]; j++; k++; } for(int n=0;n<end-start+1;n++){ arr[start+n]=tempArr[n]; } }最大公约数![]()
#include<iostream> using namespace std; int main() { long long a,b; cin>>a>>b; if (a>b) { long long t=a; a=b; b=t; } while (b%a!=0) { long long t=b; b=a; a=t%a; if (a==0) { cout<<0; return 0; } } cout<<a; return 0; }
