算法设计与分析作业
题⽬1 - 使⽤分治算法实现⼗进制⼤整数相乘
一、要求
- 给出代码（了解markdown格式如何插入⼀段代码）
- 复杂度为 。n为整数的位数。
- ⾄少包含add(a,b) minus(a,b) multiply(a,b)三个函数。
- ⾃⾏设计测试样例，测试你的程序的正确性和健壮性。给出测试结果。
二、程序如下
#include <iostream>
#include <string.h>
#include<algorithm>
using namespace std;
string multi(string number_a, string number_b) {
if(number_a=="0"||number_b=="0")return "0";
int flag1=1;
int len_a = number_a.length(); //计算长度
int len_b = number_b.length();
int* num_arr = new int[len_a+len_b];
memset(num_arr, 0, sizeof(int)*(len_a+len_b)); //置0
for (int i=len_a-1; i>=0; --i) { //计算每一位
for (int j=len_b-1; j>=0; --j) {
num_arr[i+j+1] += (number_b[j]-'0')*(number_a[i]-'0');
}
}
for (int i=len_a+len_b-1; i>=0; --i) { //进位
if (num_arr[i] >= 10) {
num_arr[i-1] += num_arr[i]/10;
num_arr[i] %= 10;
}
}
string result;
for( int i=0; i<(len_a+len_b); ++i){
if(num_arr[i]==0&&flag1)continue;
else flag1=0;
result += (char)(((int)'0')+num_arr[i]);
}
delete[] num_arr;
return result;
}
int compareNumber(string a,string b)
{
if(a.length()>b.length())return 1;
else if(a.length()<b.length())return -1;
else
{
if(a>b)return 1;
else if(a<b)return -1;
else return 0;
}
}
string add(string number_a, string number_b) {
string result;
int i;
if(compareNumber(number_a,number_b)==-1)swap(number_a,number_b);
int len_a = number_a.length(); //计算长度
int len_b = number_b.length();
int* num_arr = new int[len_a+1];
memset(num_arr, 0, sizeof(num_arr)); //置0
for (i=1; i<=len_b; i++) { //计算每一位
num_arr[len_a-i+1] = (number_b[len_b-i]-'0')+(number_a[len_a-i]-'0');
}
for(;i<=len_a;i++)
{
num_arr[len_a-i+1]=number_a[len_a-i]-'0';
}
for (int i=len_a; i>=0; --i) { //进位并转换成字符串
if (num_arr[i] >= 10) {
num_arr[i-1] += 1;
num_arr[i] %= 10;
}
if(i==0&&num_arr[0]==0)continue;
result = (char)(((int)'0')+num_arr[i])+result;
}
delete[] num_arr;
return result;
}
string Minus(string number_a, string number_b) {
string result;
int i,flag=0,flag1=1;
if(compareNumber(number_a,number_b)==-1)
{
swap(number_a,number_b);
flag=1;
}
if(number_a==number_b)return "0";
int len_a = number_a.length(); //计算长度
int len_b = number_b.length();
int* num_arr = new int[len_a+1];
memset(num_arr, 0, sizeof(num_arr)); //置0
for (i=1; i<=len_b; i++) { //计算每一位
num_arr[len_a-i+1] = (number_a[len_a-i]-'0')-(number_b[len_b-i]-'0');
}
for(;i<=len_a;i++)
{
num_arr[len_a-i+1]=number_a[len_a-i]-'0';
}
for (int i=len_a; i>=1; --i) { //进位并
if (num_arr[i] < 0) {
num_arr[i-1]--;
num_arr[i] += 10;
}
}
for (int i=0; i<=len_a; i++) { //转换成字符串
if(num_arr[i]==0&&flag1)continue;
else flag1=0;
result += (char)(((int)'0')+num_arr[i]);
}
if(flag)result="-"+result;
delete[] num_arr;
return result;
}
void addzone(string &number,int num)
{
while(num--)
{
number+="0";
}
}
string multi1(string number_a,string number_b)
{
string a0,a1,b1,b0,c0,c1,c2,a2,b2;
int half;
int len_a=number_a.size();
int len_b=number_b.size();
if(len_a<=2||len_b<=2)return multi(number_a,number_b);
if(len_a<len_b)return multi1(number_b,number_a);
if(len_a==0||len_b==0)return "";
if(len_a/2>=len_b)half=len_b-1;
else half=len_a/2;
a1=number_a.substr(0,len_a-half);
a0=number_a.substr(len_a-half,half);
b1=number_b.substr(0,len_b-half);
b0=number_b.substr(len_b-half,half);
c1=multi1(a1,b1);
c0=multi1(a0,b0);
a2=add(a1,a0);
b2=add(b0,b1);
c2=multi1(a2,b2);
c2=Minus(c2,c1);
c2=Minus(c2,c0);
addzone(c1,half*2);
addzone(c2,half);
string result=add(add(c1,c0),c2);
return result;
}
bool checkNumberValid(string a,string b)
{
for(int i=0;i<a.length();i++)
{
if(i==0&&(a[i]<=57&&a[i]>=48||a[i]==45))continue;
if(a[i]>57||a[i]<48)return false;
}
for(int i=0;i<b.length();i++)
{
if(i==0&&(b[i]<=57&&b[i]>=48||b[i]==45))continue;
if(b[i]>57||b[i]<48)return false;
}
return true;
}
int main(void){
string number_a,number_b;
int index=1;
while(cin>>number_a>>number_b)
{
cout<<"第"<<index++<<"次"<<endl;
if(!checkNumberValid(number_a,number_b))
{
cout<<"Please input the Valid Number"<<endl<<endl;
continue;
}
// cout << number_a << " * " << number_b << " = " <<multi(number_a, number_b) <<endl;
cout<<number_a<<"+"<<number_b<<"="<<add(number_a,number_b)<<endl;
cout<<number_a<<"-"<<number_b<<"="<<Minus(number_a,number_b)<<endl;
cout << number_a << " * " << number_b << " = " <<multi1(number_a, number_b) <<endl;
cout<<endl;
}
return 0;
}
测试样例：
55513513133535351 3513535133135133
535 123
153153 253
25 0
0 135513
22222 22222
2a 122
2153 222c
5555555555555555555555555555555555555555555555555 44444 555555
111111111111111111111111111111111888888888888888888888888888888888888888888
三、完成情况如下
任务0：给出代码。完成
任务1 ：复杂度为 。n为整数的位数。multi1采用Karatsuba算法实现乘法的优化。完成
2. ⾄少包含add(a,b) minus(a,b) multiply(a,b)三个函数。完成
3. ⾃⾏设计测试样例，测试你的程序的正确性和健壮性。给出测试结果。
a.正确性判断
我拿出科学计算器测试了程序的加法，减法，乘法与程序运行结果一致。
b.健壮性
- 1.当输入的字符串里面含有非法字符会提示："Please input the Valid Number 并等待下一次输出。
- 2.同时该算法也支持负数计算
- 3.自动去除多余的零
题⽬2 - ⽤快速排序思想写⼀个分治的查找第K⼩元素的程序
一、要求
- 给出代码
- 给出证明代码可以正确运⾏的截图
- 分析最坏复杂度和平均复杂
二、程序
#include<iostream>
#include<stdlib.h>
using namespace std;
int a[101],n;
void quickFind(int left,int right,int k)
{
int i,j,t,temp;
if(left>right)return;
i=left,j=right;
while(i!=j)
{
//顺序很重要，要先从右往左找
while(a[j]>=a[left]&&i<j)j--;
//从左往右找
while(a[i]<=a[left]&&i<j)i++;
//找到后交换两个数的位置
if(i<j)swap(a[i],a[j]);
}
//最后将基准数归位
swap(a[i],a[left]);
if(k==i)cout<<a[k]<<endl;
else if(k<i)quickFind(left,i-1,k);//处理左边
else quickFind(i+1,right,k);//处理右边
}
int main()
{
int k;
while(1)
{
cout<<"请输入数组的大小:"<<endl;
cin>>n;
cout<<"请输入"<<n<<"个实数"<<endl;
for(int i=1;i<=n;i++)cin>>a[i];
cout<<"请输入一个整数表示要求的第k小的："<<endl;
cin>>k;
if(k<1||k>n)
{
cout<<"请输入有效数字"<<endl;
continue;
}
cout<<"第"<<k<<"小的数字为：";
quickFind(1,n,k);
system("pause");
system("CLS");
}
return 0;
}
样例与输出
样例
11
153351 131 513 135 15 35 1351 3513 15353 11 22
4
输出
这个算法的平均时间复杂度是O ( n ) 的，每一次快排为n,在有序下平均c次即可找到（c为常量），但在最坏情况下的时间复杂度是O ( n 2 )比如：9 8 7 6 5 4 3 2 1，求第9大。
