实验一：
1用分治法实现一组无序序列的两路合并排序和快速排序。 要求清楚合并排序及快速排 序的基本原理， 编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。
2采用基于“五元中值组取中值分割法”（median-of-median-of-five partitioning） 的线性
时间选择算法，找出 N 个元素集合 S 中的第 k 个最小的元素，使其在线性时间内解决。（参
考教材 5.5.3 节）
分治法采用将一个难以直接求解的复杂问题分解成若干个规模较小、相互独立，但类型相同的子问题，直到子问题足够小，能够直接求解为止，然后求解这些子问题，并且将子问题的解合成原始问题的一个完整解的策略。基于这样一种策略，我们可以用它来解决一系列复杂的问题。对于排序问题，将原来的序列分成一个个子序列后分别进行排序，再将已排序的子序列合成一个有序序列是可行的，所以符合分治法策略。不过，合并排序和快速排序虽然都运用分治策略，但两者的角度不同，得到的排序算法也不相同。合并排序的问题分解过程十分简单，只需将序列一分为二即可：而快速排序的问题分解方法相对较困难，需调用Partition函数将一个序列划分为子序列。然而，从子问题解得到原问题解的过程对于快速排序来说异常简单，几乎无须额外的工作；但对于合并排序，则需要调用Merge函数来实现。所以，其实Partition函数和Merge函数是这两种排序算法的核心。而线性时间选择第k小元素这个算法我觉得也是受到了快速排序中的分划方法的启迪，采用分治法策略去求。
1.合并排序与快速排序
#include<iostream>
#include<fstream>
#define INFTY 2147483647;
using namespace std;
class SortableList
{
public:
SortableList(int mSize)
{
maxSize = mSize;
l = new int[maxSize];
n = 0;
}
~SortableList()
{
delete[] l;
}
void Input();
void Output();
void MergeSort();
void QuickSort();
private:
int *l;
int maxSize;
int n;
void Merge(int left,int mid,int right);
void MergeSort(int left,int right);
void QuickSort(int left, int right);
void Swap(int i,int j);
int Partition(int left, int right);
};
void SortableList::Merge(int left,int mid,int right)
{
int *temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while((i<=mid)&&(j<=right))
if(l[i]<=l[j])
temp[k++] = l[i++];
else
temp[k++] = l[j++];
while(i<=mid) //将剩余元素输出
temp[k++] = l[i++];
while(j<=right)
temp[k++] = l[j++];
for (i = 0, k = left; k <= right;) //将排好序的有序序列复制到原序列中去
l[k++] = temp[i++];
}
void SortableList::MergeSort()
{
MergeSort(0,n-1);
}
void SortableList::MergeSort(int left,int right)
{
if(left<right)
{
int mid = left + (right-left) / 2;
MergeSort(left,mid);
MergeSort(mid+1,right);
Merge(left,mid,right);
}
}
void SortableList::Swap(int i,int j)
{
int temp = l[i];
l[i] = l[j];
l[j] = temp;
}
int SortableList::Partition(int left,int right)
{
int i = left, j = right + 1;
l[n]=INFTY;
do{
do
i++;
while (l[i]<l[left]);
do
j--;
while (l[j]>l[left]);
if(i<j)
Swap(i,j);
} while (i < j);
Swap(left,j);
return j;
}
void SortableList::QuickSort()
{
QuickSort(0,n-1);
}
void SortableList::QuickSort(int left,int right)
{
if(left<right)
{
int j = Partition(left,right);
QuickSort(left,j-1);
QuickSort(j+1,right);
}
}
// void SortableList::Input()
// {
// for (int i = 0; i < maxSize;i++)
// {
// cin >> l[i];
// n++;
// }
// }
void SortableList::Input()
{
int i = 0;
ifstream out ("Sort.txt");
if(!out)
{
cout << "Can not open output file.\n";
return;
}
for (i = 0; i < maxSize;i++)
{
out >> l[i];
n++;
}
out.close();
}
void SortableList::Output()
{
for (int i = 0; i < maxSize;i++)
{
cout << l[i] << " ";
// cout << endl;
}
}
int main()
{
int key;
int x, k;
SortableList list(30);
cout << "原始序列：\n" << endl;
list.Input();
list.Output();
cout << "\n\n请选择排序算法：【0】两路合并排序 【1】快速排序\n" << endl;
cin >> key;
if(key==0)
{
list.MergeSort();
}
else
list.QuickSort();
cout << "排序后的序列：\n\n";
list.Output();
}
2.选择第k小元素
求第k小元素其实可以直接通过排序算法将原序列排序好，然后取出第k小元素即可，但是这样的话在最坏情况下的时间复杂度就不是线性的了，比如采用快速排序，那么在最坏情况下时间复杂度为O(n^2)。人们并不满足与这样的时间复杂度，所以继续去优化这样的一个算法，采用二次取中法确定主元的方式使得分划所得的两个子集合的大小相对接近，从而避免了上述最坏情况的发生，使得最坏情况下的时间复杂度也是O(n),我想这就是算法设计与分析的魅力所在，通过应用或设计一种算法去不断优化时空复杂度。
#include <iostream>
#include <fstream>
#define INFTY 2147483647;
using namespace std;
class SortableList
{
public:
SortableList(int mSize)
{
maxSize = mSize;
l = new int[maxSize];
n = 0;
}
~SortableList()
{
delete[] l;
}
void Input();
void Output();
void MergeSort();
int Select(int& x,int k);
int Ceil(int a,int b);
private:
int *l;
int maxSize;
int n;
void Merge(int left,int mid,int right);
void MergeSort(int left,int right);
void Swap(int i,int j);
int Partition(int left, int right);
int Select(int k,int left,int right,int r);
};
void SortableList::Merge(int left,int mid,int right)
{
int *temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while((i<=mid)&&(j<=right))
if(l[i]<=l[j])
temp[k++] = l[i++];
else
temp[k++] = l[j++];
while(i<=mid) //将剩余元素输出
temp[k++] = l[i++];
while(j<=right)
temp[k++] = l[j++];
for (i = 0, k = left; k <= right;) //将排好序的有序序列复制到原序列中去
l[k++] = temp[i++];
}
void SortableList::MergeSort()
{
MergeSort(0,n-1);
}
void SortableList::MergeSort(int left,int right)
{
if(left<right)
{
int mid = left + (right-left) / 2;
MergeSort(left,mid);
MergeSort(mid+1,right);
Merge(left,mid,right);
}
}
void SortableList::Swap(int i,int j)
{
int temp = l[i];
l[i] = l[j];
l[j] = temp;
}
int SortableList::Partition(int left,int right)
{
int i = left, j = right + 1;
l[n]=INFTY;
do{
do
i++;
while (l[i]<l[left]);
do
j--;
while (l[j]>l[left]);
if(i<j)
Swap(i,j);
} while (i < j);
Swap(left,j);
return j;
}
void SortableList::Input()
{
int i = 0;
ifstream out ("Sort.txt");
if(!out)
{
cout << "Can not open output file.\n";
return;
}
for (i = 0; i < maxSize;i++)
{
out >> l[i];
n++;
}
out.close();
}
void SortableList::Output()
{
for (int i = 0; i < maxSize;i++)
{
cout << l[i] << " ";
// cout << endl;
}
}
int SortableList::Ceil(int a,int b)
{
return (int)(a / b) + 1;
}
int SortableList::Select(int&x,int k)
{
if(n<=0||k>n||k<=0)
return -1;
int j = Select(k,0,n-1,5);
x = l[j];
return 1;
}
int SortableList::Select(int k,int left,int right,int r)
{
int n = right - left + 1;
if(n<=r)
{
MergeSort(left,right);
return left + k - 1;
}
for (int i = 1; i < n / r;i++)
{
MergeSort(left+(i-1)*r,left+i*r-1);
Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);
}
int j = Select(Ceil(n/r,2),left,left+(n/2)-1,r);
Swap(left,j);
j = Partition(left,right);
if(k==j-left+1)
return j;
else if(k<j-left+1)
return Select(k,left,j-1,r);
else
return Select(k-(j-left+1),j+1,right,r);
}
int main()
{
int key;
int x, k;
SortableList list(30);
list.Input();
list.Output();
cout << "\n\n请输入要寻找的第几小元素：\n";
cin >> k;
list.Select(x,k);
cout << x << endl;
//list.Output();
}
实验二
- 用动态规划法和备忘录方法实现求两序列的 最长公共子序列问题。 要求掌握动态规划法思想在实际中的应用，分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。
- 用动态规划法和备忘录方法求解矩阵相乘问题， 求得最优的计算次序以使得矩阵连乘总的数乘次数最少，并输出加括号的最优乘法算式。
1.最长公共子序列
#include <iostream>
using namespace std;
int const MaxLen = 50;
class LCS
{
public:
LCS(int nx,int ny,char *a,char *b);
~LCS();
int LCSLength();
void CLCS();
void Output(int **a);
int** getc() // 用来访问私有数据成员
{
return c;
};
int** gets()
{
return s;
};
private:
void CLCS(int i,int j);
int **c, **s;
int m, n;
char *x, *y;
};
LCS::LCS(int nx,int ny,char *a,char *b)
{
m = nx;
n = ny;
x = a;
y = b;
c = new int *[m + 1];
s = new int *[m + 1];
for (int i = 0; i <= m;i++)
{
c[i] = new int[n + 1];
s[i] = new int[n + 1];
}
}
LCS::~LCS()
{
for (int i = 0; i < m;i++)
{
delete c[i];
delete s[i];
}
delete c;
delete s;
}
int LCS::LCSLength()
{
int i,j;
for ( i = 0; i <= m;i++)
{
c[i][0] = 0;
s[i][0] = 0;
}
for (j = 1; j <= n;j++)
{
c[0][j] = 0;
s[0][j] = 0;
}
for (i = 1; i <= m;i++)
{
for (j = 1; j <= n;j++)
{
// if(x[i]==y[i]) !!!!! 应该是y[j]
// {
// c[i][j] = c[i-1][j-1]+ 1; // 左上格值 + 1
// s[i][j] = 1;
// }
if(x[i] == y[j]) //由c[i-1][j-1]得到c[i][j]
{
c[i][j] = c[i - 1][j - 1] + 1;
s[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1]) // 左格值 > 上格值
{
c[i][j] = c[i - 1][j];
s[i][j] = 2;
}
else //左格值 < 上格值
{
c[i][j] = c[i][j - 1];
s[i][j] = 3;
}
}
}
return c[m][n]; // 返回最优解值
}
void LCS::CLCS(int i,int j)
{
if(i==0||j==0)
return;
if(s[i][j]==1)
{
CLCS(i-1,j-1);
cout << x[i];
}else if(s[i][j]==2)
CLCS(i-1,j);
else
CLCS(i, j - 1);
}
void LCS::CLCS()
{
CLCS(m,n);
}
void LCS::Output(int **a)
{
int i, j;
printf(" ");
for (i = 0; i <= n;i++)
{
printf("%4d",i);
}
printf("\n");
for (i = 0; i <= m;i++)
{
printf("%2d",i);
for (j = 0; j <= n;j++)
{
printf("%4d",a[i][j]);
}
printf("\n");
}
}
int main()
{
// int nx = 7, ny = 6;
// char *x = (char*)"0abcbdab";
// char *y = (char*)"0bdcaba";
int nx, ny;
char *x = new char[MaxLen], *y = new char[MaxLen];
cout << "Please input X:(Start with 0, like 0ab)" << endl;
scanf("%s", x);
nx = strlen(x)-1;
cout <<endl<< "Please input Y:(Start with 0, like 0ab)" << endl;
scanf("%s", y);
ny = strlen(y)-1;
LCS lcs(nx, ny, x, y);
cout <<endl<< "The LCSLength of X and Y is: " << lcs.LCSLength() << endl<<endl;
cout << "The CLCS is: " ;
lcs.CLCS();
cout << endl;
cout <<endl<< " c = " << endl<<endl;
lcs.Output(lcs.getc()); // 输出c[i][j]
cout <<endl<<endl<< " s = " << endl<<endl;
lcs.Output(lcs.gets()); // 输出s[i][j]
delete []x;
delete []y;
return 0;
}
2.矩阵连乘
#include <iostream>
#include <iomanip> //输出格式头文件
using namespace std;
int const MaxLen = 50;
class MatrixChain
{
public:
MatrixChain(int mSize,int *q);
int MChain();
int LookupChain();
void Traceback();
void Output();
private:
void Traceback(int i,int j);
int LookupChain(int i,int j);
int *p, **m, **s, n;
};
MatrixChain::MatrixChain(int mSize, int *q)
{ n=mSize;
m=new int*[n]; s=new int*[n]; p=new int[n+1];
for(int i=0; i<n; i++)
{ m[i]=new int [n]; m[i][i]=0;
s[i]=new int [n]; s[i][i]=0;
p[i]=q[i];
}
p[n]=q[n];
}
int MatrixChain::MChain()
{ //求A[0:n-1]的最优解值
//for (int i=0;i<n; i++) m[i][i]=0; //由于构造函数中有了m[i][i]=0的语句，这条可以删除，且备忘录方法输出的s数组对角线就是0，否则不正确。
for (int r=2; r<=n; r++)
for (int i=0; i<=n-r; i++)
{ int j=i+r-1;
m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; //m[i][j] 的初值
s[i][j]=i;
for (int k=i+1; k<j; k++)
{ int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if (t<m[i][j])
{ m[i][j]=t; s[i][j]=k;
}
}
}
return m[0][n-1];
}
void MatrixChain::Traceback(int i,int j)
{
if(i==j)
{
cout << 'A' << i;
return;
}
if(i<s[i][j])
cout << '(';
Traceback(i,s[i][j]);
if(i<s[i][j])
cout << ')';
if(s[i][j]+1<j)
cout << '(';
Traceback(s[i][j]+1,j);
if(s[i][j]+1<j)
cout << ')';
}
void MatrixChain::Traceback()
{
cout << '(';
Traceback(0,n-1);
cout << ')';
cout << endl;
}
int MatrixChain::LookupChain(int i, int j)
{ if (m[i][j]>0) return m[i][j]; //子问题已经求解，直接引用
if(i==j) return 0; //单一矩阵无须计算
int u=LookupChain(i+1, j)+p[i]*p[i+1]*p[j+1]; //按式（7-9）求最小值
s[i][j]=i;
for (int k=i+1; k<j; k++)
{ int t=LookupChain(i, k)+LookupChain(k+1, j)+p[i]*p[k+1]*p[j+1];
if (t<u)
{ u=t; s[i][j]=k;
}
}
m[i][j]=u; return u; //保存并返回子最优解值
}
int MatrixChain::LookupChain()
{
return LookupChain(0, n-1); //返回A[0:n-1]的最优解值
}
void MatrixChain::Output()
{ int i,j;
cout<<" m="<<endl;
cout<<" ";
for(j=0; j<n; j++)
if(j<2) cout<<setw(4)<<j;
else cout<<setw(6)<<j;
cout<<endl;
for(i=0; i<n; i++)
{ cout<<" "<<i<<" ";
for(j=0; j<n; j++)
{ if(i<j) cout<<setw(6)<<m[i][j]; //setw(6), 指定输出域宽为6
else if(i==j) cout<<setw(2)<<m[i][j];
else cout<<setw(6)<<" ";
}
cout<<endl;
}
cout<<" s="<<endl;
cout<<" ";
for(j=0; j<n; j++) cout<<j<<" ";
cout<<endl;
for(i=0; i<n; i++)
{ cout<<" "<<i<<" ";
for(j=0; j<n; j++)
{ if(i<=j) cout<<s[i][j]<<" ";
else cout<<" ";
}
cout<<endl;
}
}
int main()
{
// int nn=6,k,k2;
// int pp[7]={30,35,15,5,10,20,25};
int pp[MaxLen];
int nn,i,k, k2;
cout << " 请输入连乘矩阵的个数" << endl;
scanf("%d", &nn);
cout << " 请输入连乘矩阵的"<<nn+1<<"个维数(以空格隔开)"<< endl;
for (i = 1; i <= nn+1;i++)
{
scanf("%d", &pp[i-1]);
}
MatrixChain mm(nn, pp);
k = mm.MChain();
cout << " 最少数乘次数k=" << k << endl; //最少数乘次数k=15125
mm.Traceback(); //矩阵连乘次序:(((A0(A1A2))((A3A4)A5))
cout << endl;
mm.Output();
k2 = mm.LookupChain();
cout <<endl<< "采用备忘录方法：" << endl;
cout << " 最少数乘次数k2=" << k2 << endl; //最少数乘次数k=15125
mm.Traceback(); //矩阵连乘次序:(((A0(A1A2))((A3A4)A5))
cout << endl;
mm.Output();
}
实验三
用回溯法求解 8- 皇后问题，使放置在 8*8 棋盘上的 8 个皇后彼此不受攻击，即：任何两个皇后都不在同一行、同一列或同一斜线上。请输出 8-皇后问题的所有可行解。
用回溯法编写一个递归程序解决如下装载问题： 有 n 个集装箱要装上 2 艘载重分别为 c1和 c2的轮船，其中集装箱 i 的重量为 wi（1≤ i ≤ n） ，且 ,问是否有一个合理的装载方案可以将这 n 个集装箱装上这 2 艘轮船？如果有，请给出装载方案
提示 ：参考 子集和数问题的求解方法。
举例 ： 当 n=3， c1=c2=50， 且 w=[10,40,40]时， 可以将集装箱 1 和 2 装到第一艘轮船上，集装箱 3 装到第二艘轮船上；如果 w=[20,40,40]时，无法将这 3 个集装箱都装上轮船。
1.8皇后问题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define N 8 // 8 皇后
using namespace std;
int count = 0,count2=0;
//判定两个皇后是否在同一列或在同一斜线上
bool Place(int k, int i, int *x)
{
for(int j = 0; j < k; j++)
if((x[j] == i) || (abs(x[j] - i) == abs(j - k)))
return false;
return true;
}
//递归函数（求解n皇后问题）
void NQueens(int k, int n, int *x)
{
for(int i = 0; i < n; i++) //显式约束的第一种观点，x[k] = 0,1,···,n-1
{
if(Place(k, i, x)) //约束函数
{
x[k] = i;
if(k == n - 1)
{
for(i = 0; i < n; i++)
cout << x[i] << " "; //输出一个可行解
cout << endl;
count ++;
}
else
{
NQueens(k + 1, n, x); //深度优先进入下一层
}
}
}
}
void NQueens(int n, int *x)
{
NQueens(0, n, x);
}
//求非对称解
void NQueens2(int k, int n, int *x)
{
static int temp=n; //求非对称的解
if(k==0)
n = int(temp / 2);
else
n = temp;
for(int i = 0; i < n; i++) //显式约束的第一种观点，x[k] = 0,1,···,n-1
{
if(Place(k, i, x)) //约束函数
{
x[k] = i;
if(k == n - 1)
{
for(i = 0; i < n; i++)
cout << x[i] << " "; //输出一个可行解
cout << endl;
count2 ++;
}
else
{
NQueens2(k + 1, n, x); //深度优先进入下一层
}
}
}
}
void NQueens2(int n, int *x)
{
NQueens2(0, n, x);
}
int main()
{
int queens[N]; //8皇后
// int count = 0,count2=0;
for(int i = 0; i < N; i++)
queens[i] = -1;
NQueens(N, queens);
cout <<endl<< "可行解共有: " << count <<" 组"<< endl;
cout << endl<< " 仅输出非对称解 : " << endl;
NQueens2(N, queens);
cout <<endl<< "非对称可行解共有: " << count2 <<" 组"<< endl;
getchar();
return 0;
}
2.装载问题
#include <iostream>
using namespace std;
template <class T>
class Loading
{
private:
int n, // 集装箱数
x[100], // 当前解
bestx[100]; // 当前 第一艘 船的最优解
T c1, // 第一艘轮船的核定载重量
c2, // 第二艘轮船的核定载重量
w[100], // 集装箱重量数组
total, // 所有集装箱重量之和
cw, // 当前 第一艘船的 载重量
bestw, // 当前 第一艘 船的最优载重量
r; // 剩余集装箱总重量
public:
Loading() // 构造函数
{
cout<<"请输入集装箱的数量："<<endl;
cin>>n;
cout<<"请输入轮船1、2的载重量："<<endl;
cin>>c1>>c2;
cout<<"请输入每个集装箱的重量："<<endl;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
r=0;
cw=0;
bestw=0;
for(int i=1;i<=n;i++)
{
r=r+w[i];
}
}
~Loading() // 析构函数
{
}
void Backtrack(int i); // 找到最接近第一艘轮船载重c1 的最佳装载方案，
// 最优载重值bestw ，最优解数组bestx 。
void Show(); // 输出整个装载方案
};
template <class T>
void Loading<T>::Backtrack(int i)
{
if(i>n) //判断是否达到叶子节点
{ //到达叶子节点
if(cw>bestw)
{
for(int j=1;j<=n;j++)
{
bestx[j]=x[j]; //把当前解赋给最优解
}
bestw=cw; //把当前载重量赋给当前最优载重量
}
}
r=r-w[i]; //剩余集装箱的总重量
if(cw+w[i]<=c1) //判断该集装箱到底放不放
{
x[i]=1;
cw=cw+w[i];
Backtrack(i+1);
//当节点i的子树延伸结束时要返回i节点
x[i]=0;
cw=cw-w[i];
}
if(cw+r>bestw) //判断先不放该集装箱后是否还有可行解
{
x[i]=0;
Backtrack(i+1);
}
r=r+w[i];
}
template <class T>
void Loading<T>::Show()
{
int c2w=0;
for(int i=1;i<=n;i++)
{
if(bestx[i]==0)
{
c2w=c2w+w[i];
}
}
if(c2w>c2)
cout<<endl<<"装载失败！无法装下所有的集装箱！"<<endl;
else
{
cout << endl<<"成功装载！" << endl;
cout<<"第一艘船所装的集装箱为："<<endl;
for(int i=1;i<=n;i++)
{
if(bestx[i]==1)
cout<<i<<" ";
}
cout<<endl;
cout<<"第二艘船所装的集装箱为："<<endl;
for(int i=1;i<=n;i++)
{
if(bestx[i]!=1)
cout<<i<<" ";
}
}
}
int main()
{
Loading<int> load;
load.~Loading();
load.Backtrack(1);
load.Show();
// system("pause");
return 0;
}
实验四
编程一个简单的RSA加、解密系统。
假设用户A选择两个素数p和q，计算得到n=pq和Φ(n)=(p-1)(q-1)。选择一个加密密钥e，它小于Φ(n)且与Φ(n)互素。计算解密密钥 d≡ e-1 mod Φ(n)。则用户A公布公开密钥{e,n}，自己拥有私有密钥{d,n}。
用户B使用用户 A 的公开密钥 e 和 n 对报文 M 进行加密，得到 C= Me mod n，并发送给用户 A。
用户A收到加密的报文后，使用自己的私有密钥 d 和 n 对加密报文 C 进行解密，恢复得到明文 M=Cd mod n。
初始代码
#include <iostream>
using namespace std;
int MOD;
//由公开密钥e和n，求私有密钥d
int ext_euclid(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int gcd = ext_euclid(b, a % b, x, y);
int t = x % MOD;
x = y % MOD;
y = ((t - a / b * x) % MOD + MOD) % MOD;
return gcd;
}
int main()
{
int p, q, i, d;
cout << "请输入一个质数 p (如 101) :";
cin >> p;
cout << "请输入一个质数 q (如 113) :";
cin >> q;
int n = p * q;
cout<<"分组加密时，每个分组的大小 n 不能超过 p*q=";
cout << n << endl;
//求得φ(n)=(p-1)*(q-1)的值
MOD = (p - 1) * (q - 1);
cout << "模φ(n)=(p-1)*(q-1)=";
cout << MOD << endl << endl;
//选取与φ(n)互质的公钥e
int e;
cout << "输入与φ(n)互质的公钥 e (如 3533):";
cin >> e;
//由e和φ(n)生成私钥d
int x, y;
ext_euclid(e, MOD, d, y);
while(d < 0)
d += MOD;
cout << "通过调用扩展欧几里德算法，求得密钥d为：" << d << endl;
//利用生成的公钥{e,n}对明文M进行加密
int M, C;
cout << "现在公钥{e,n}、私钥{d,n}均已生成完毕。\n\n请输入需要传输的明文内容进行加密(如9726):";
cin >> M;
C = 1;
for(i = 1; i <= e; i++)
C = C * M % n;
cout <<endl<< "-------------------- 加解密完成 ----------------------" << endl<<endl;
cout << "明文M= " << M << " 经加密后得到密文C=M^e(mod n): " << C << endl;
//利用生成的私钥私钥{e,n}对密文C进行解密
M = 1;
for(i = 1; i <= d; i++)
M = M * C % n;
cout << "密文C= " << C << " 经解密后得到明文M=C^d(mod n): " << M << endl;
return 0;
}
更新
由于第四次实验是在考试周的时候做的，对于RSA的原理也不是很清楚，上面的代码也是借鉴了网上的，自己实验时发现样例能正常运行，但是有的例子没办法正常解码，最近有空又重新研究了一下RSA，记录如下。
原理
1.公钥与私钥的生成
（1）选取两个大素数：p和q,(p≠q)；
（2）计算n=p*q；
（3）利用欧拉(Euler)函数的性质与定理计算Φ(n)=(p-1)·(q-1)
欧拉函数 设n是自然数，数列1，2，···，n-1中与n互素的数的个数称为n的欧拉函数，记为Φ(n)
- 性质 若p是素数，则Φ(p)=(p-1)
- 定理 设p和q是素数，对n=pq，有Φ(n)=Φ(p)Φ(q)=p-1)·(q-1)
（4）随机选择加密密钥e(公钥)，使 gcd(Φ(n),e)=1; 1<e<Φ(n)
（5）最后，利用Euclid（欧几里得）算法计算解密密钥d，使其满足ed=1（mod Φ(n)）。
后来自己重新敲代码的时候对这一步产生了误解，因为书上给的公式是d=e^(-1)modΦ(n),我把e^(-1)理解成-1次幂了。后来重新看书和查资料，这里描述的应该是e和d是互逆的关系，e^(-1)指的是e是d关于模Φ(n)的乘法逆元
乘法逆元 设a是整数，若存在x使得ax≡1(mod n),则称a与x互逆，x是a关于模n的乘法逆元(inverse),记为x=a^(-1)
然后将（e，n）公开，即为公钥PK，私人保存好d，即为私钥SK。
2.加密与解密
加密公式为
$$
C=M^e mod n
$$
解密公式为
$$
M^`=C^d mod n
$$
一般在计算M^e modn的时候都是计算M mod n然后累乘 e次，这是按模计算原理的推论。
重新敲的代码
针对之前代码中出现的部分样例解密失败的问题，我认为与未对输入的素数和公钥e与Φ(n)是否互质进行检验有很大关系，于是在新的代码中加入了 JudgePrime 和 IsCoprime 分别进行判断，经过测试，成功解决了之前的解密失败问题（但是对于密文长度较长的情况还是会失败，目前未找到原因）:sob:
#include <iostream>
using namespace std;
int MOD;
int JudgePrime(int x)
{
if(x == 1) return 1;
for(int i=2;i <=x/2;i++)
{
if(x % i == 0)
return 0;
}
return 1;
}
bool isCoprime(int x,int y)
{
if(x==1 && y==1)//1和1互质
return true;
else if(x<=0 || y<=0 || x==y)//非正整数都不存在互质的说法
return false;
else if(x==1 || y==1)//1和任何正整数都互质
return true;
else
{
int tmp=0;
//使用求商判断法，如果输入的x<y，第一次循环会交换x和y的位置
while(true)
{
tmp=x%y;
if(tmp==0)
{
break;
}
else
{
x=y;
y=tmp;
}
}
if(y==1) //最大公约数为1,所以互质
return true;
else //最大公约数大于1，所以不互质
return false;
}
}
//由公开密钥e和n，求私有密钥d
int ext_euclid(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int gcd = ext_euclid(b, a % b, x, y);
int t = x % MOD;
x = y % MOD;
y = ((t - a / b * x) % MOD + MOD) % MOD;
return gcd;
}
int main()
{
int p,q,n,e,d;
cout<<"请输入第一个大素数p："<<endl;
cin>>p;
while(!JudgePrime(p))
{
cout<<"【 抱歉，您输入的不是素数，请重新输入！】"<<endl;
cin>>p;
}
cout<<"请输入第二个大素数q："<<endl;
cin>>q;
while(!JudgePrime(q))
{
cout<<"【 抱歉，您输入的不是素数，请重新输入！】"<<endl;
cin>>q;
}
n=p*q;
cout<<"\n乘积 n=p*q= "<<n<<endl;
MOD=(p-1)*(q-1);
cout<<"φ(n)=(p-1)(q-1)= "<<MOD<<endl;
cout<<"\n请输入一个与φ(n)互质的公钥e: "<<endl;
cin>>e;
while(!isCoprime(e,MOD))
{
cout<<"【 e与φ(n)不互质，请重新输入！】"<<endl;
cin>>e;
}
//由e和φ(n)生成私钥d
int x, y;
ext_euclid(e, MOD, d, y);
while(d < 0)
d += MOD;
cout << "\n通过调用扩展欧几里德算法，求得密钥d为：" << d << endl;
//利用生成的公钥{e,n}对明文M进行加密
int M, C;
cout << "现在公钥{e,n}、私钥{d,n}均已生成完毕。\n\n请输入需要传输的明文内容进行加密:";
cin >> M;
cout <<endl<< "-------------------- 加解密完成 ----------------------" << endl<<endl;
C = 1;
for(int i = 1; i <= e; i++)
C = C * M % n;
cout << "明文M= " << M << " 经加密后得到密文C=M^e(mod n): " << C << endl;
//利用生成的私钥私钥{e,n}对密文C进行解密
M = 1;
for(int i = 1; i <= d; i++)
M = M * C % n;
cout << "密文C= " << C << " 经解密后得到明文M=C^d(mod n): " << M << endl;
return 0;
}
