算法导论部分源码 经典

// WhetherEqualSum.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> using namespace std; const int MAX = 100000; void MergeSort(int A[],int p,int r); void merge(int A[],int p,int q,int r); bool isFound(int a[],int n,int sum,int *oneNumPt,int *anoNumPt); int main(int argc, char* argv[]) { int A[]={4,8,2,1,9,3,7,11,10,6,14,5}; //给定一个输入序列保存于数组A[]中 int temp[12]; //临时保存输入的序列A[]中的元素，以后的操作都在temp[]上做 for(int i=0;i<12;i++) //把数组A[]全部复制给temp[] { temp[i] = A[i]; } MergeSort(temp,0,11); //归并排序 cout<<"排序之前的序列为："<<endl; for(i=0;i<12;i++) //输出排序前的结果 { cout<<A[i]<<' '; } cout<<endl; cout<<"排序之后的序列为："<<endl; for(i=0;i<12;i++) //输出排序后的结果 { cout<<temp[i]<<' '; } cout<<endl; int *addend1Pt = new int; //其中一个加数 int *addend2Pt = new int; //其中另一个加数 int sum; //给定的和 cout<<"请输入需要的和"; cin>>sum; if(isFound(temp,12,sum,addend1Pt,addend2Pt)) { cout<<"存在这样的两个数。"<<endl; cout<<"加数和被加数分别为："<<endl; cout<<*addend1Pt<<" "<<*addend2Pt<<endl; } else { cout<<"不存在这样的两个数。"<<endl; } return 0; } void MergeSort(int A[],int p,int r) //归并排序 { int q; if(p<r) { q = (p+r)/2; MergeSort(A,p,q); MergeSort(A,q+1,r); merge(A,p,q,r); } } void merge(int A[],int p,int q,int r) //归并 { //p:开始元素的下标,r:结束元素的下标,q:归并点元素的下标 int n1=q-p+1; //n1为A[p..q]这个已排好序列中元素的个数 int n2=r-q; //n2为A[q+1..r]这个已排好序列中元素的个数 int L[100]; //看作是L[1..n1+1] int R[100]; //看作是R[1..n2+1] for(int i=1;i<=n1;i++) //元素拷贝 { L[i]=A[p+i-1]; } for(int j=1;j<=n2;j++) //元素拷贝 { R[j]=A[q+j]; } L[n1+1]=MAX; //设置观察哨 R[n2+1]=MAX; //设置观察哨 i=1;j=1; for(int k=p;k<=r;k++) //归并的核心代码 { if(L[i]<R[j]) { A[k]=L[i]; i=i+1; } else { A[k]=R[j]; j=j+1; } } } bool isFound(int a[],int n,int sum,int *oneNumPt,int *anoNumPt) //给定一个数组a[],数组的长度为n,给定的和为sum,看数组里是否存在两个数的和恰好为sum { //oneNumPt和anoNumPt用来返回满足和为sum的两个加数 int head = 0; int tail = n-1; while(head!=tail) { if(a[head]+a[tail]<sum) { head ++; } else if(a[head]+a[tail]>sum) { tail --; } else { *oneNumPt = a[head]; *anoNumPt = a[tail]; return true; } } return false; }