一步步学算法(算法题解)---5

时间:2022-04-11 03:20:34

本人大二,最近开始自学算法,在此记录自己学习过程中接触的习题。与君共勉。

水平有限,目前涉及的题目都比较水。

题目分布为5+1.  5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。


一步步学算法(算法题解)---5

算式求值。


1.数字重组。

问题描述:

键盘输入一个高精度的正整数N(不超过230位), 去掉其中任意S个数字后, 剩下的数字按原左右次序将组成一个新的正整数. 编程对给定的N和S, 寻找一种方案使得剩下数字组成的新数最小. 

例子:设N=6453023456,S=6,则重组过程如下:

(1) 去掉6,N=453023456;
(2)
去掉5, N=43023456;
(3)
去掉4, N=3023456;

(4) 去掉3, N=23456;

(5) 去掉56,N=234. 

问题分析:

分析:从以上例子中可以看出,可用如下步骤来实现该重组过程:

(1)从左边开始遍历S:若满足N[i]>N[i+1]则去掉N[i]并结束该次遍历;若N[i+1]!='\0'并且遍历次数小于S则重复(1);

(2) 若已删除掉的数(TIME)的个数小于S,则直接从N的右边删除S-TIME个未被筛选的数字.

#include<stdio.h>
#include<string.h>
void find()
{
char N[200];
int s;
int i=0,j;
printf("input the number:");
scanf("%s",N);
printf("\ninput times:");
scanf("%d",&s);
while(s>0) /*循环减s次*/
{
printf("%c",N[5]);

i=0; /*每次删除后重头开始*/
while (i<strlen(N) && N[i]<=N[i+1])
i++; /*算法核心*/
for (j=i; j<strlen(N); j++)
N[j]=N[j+1]; /*移位将删除的覆盖*/
s--;
}
printf("%s",N);

}

int main()
{
find();
return 0;
}

二  大数加法。

思路很常规。先用字符数组录入大数,(这个时候高位存在数组下标小的位置。  如:最高位在arr[0]处。  ---输入方式原因)  

然后再从高往低反向存入整数数组中。(使得低位在数组下标小的位置,符合常规。)

然后在进行计算,考虑进位情况。

加法比较简单,就不多说什么了。  直接上代码。

#include <stdio.h>
#include <string.h>
#define MAXLEN 1000

int main()
{
char a1[MAXLEN];
char a2[MAXLEN];
static int v1[MAXLEN];
static int v2[MAXLEN];
static int v3[MAXLEN];
int i,j,n,L,z;

scanf("%d",&n); //读入计算的组数
for (j=0;j<n;j++)
{
scanf("%s%s",a1,a2); //读入每组计算的2个大数

L=strlen(a1);
for (i=0;i<L;i++)
v1[i]=a1[L-1-i]-'0'; //大数a1反向

L=strlen(a2);
for (i=0;i<L;i++)
v2[i]=a2[L-1-i]-'0'; //大数a2反向

for (i=0;i<MAXLEN;i++)
v3[i]=v1[i]+v2[i]; //a1.a2各位直接相加,先不考虑进位

for (i=0;i<MAXLEN;i++)
{
if (v3[i]>=10)
{
v3[i+1]+=v3[i]/10; //对每位进行进位处理
v3[i]=v3[i]%10;
}
}

printf("Case %d:\n", j+1);
printf("%s + %s = ", a1, a2);

z=0;
for (i=MAXLEN-1;i>=0;i--) //打印
{
if (z==0)
{
if (v3[i]!=0)
{
printf("%d",v3[i]);
z=1;
}
}
else
{
printf("%d",v3[i]);
}
}
if (z==0) printf("0");

printf("\n");
}
return 0;
}



三  大数减法。

大数减法的处理思路和加法差不多。先判断a,b两数的大小,然后按条件进行逐位计算,并且处理借位。此时借位的条件是某位的值小于0,则往前借位。

思路很常规,也不难,直接上代码。

水平有限,现在只能写出这样比较麻烦的算法。   希望。以后有能力了,有时间了再去优化。

#include<stdio.h>
#include<string.h>

int compare(char *str_a,char *str_b)
{
int len_a, len_b;
len_a = strlen(str_a); //分别获取大数的位数进行比较
len_b = strlen(str_b);

if ( strcmp(str_a, str_b) == 0 ) //返回比较结果
return 0;
if ( len_a > len_b )
return 1;
else if( len_a == len_b )
return strcmp(str_a, str_b);
else
return -1;
}

int main()
{
int f, n;
int i, k, len_a, len_b;
char str_a[1000], str_b[1000];
int num_a[1000] = {0}; //初始化大数数组,各位全清0
int num_b[1000] = {0};
int num_c[1000];

while (scanf("%s%s",str_a,str_b)!= EOF) //可进行多组测试
{
len_a = strlen(str_a); //分别获得两个大数的位数
len_b = strlen(str_b);

k = len_a > len_b? len_a:len_b; //获得最大的位数
num_c[0] = 0;
f = 0;
n = compare(str_a,str_b);

for (i=0;i<len_a;i++) //颠倒存储
num_a[i] = str_a[len_a-i-1] - '0';
for (i=0;i<len_b;i++)
num_b[i] = str_b[len_b-i-1] - '0';

for (i=0;i<k;i++) //逐位进行减法
{
if (n>=0)
{
if (num_a[i] >= num_b[i])
num_c[i] = num_a[i] - num_b[i];
else
{
num_c[i] = num_a[i] - num_b[i] + 10;
num_a[i+1]--;
}
}
else
{
if ( num_b[i] >= num_a[i])
num_c[i] = num_b[i] - num_a[i];
else
{
num_c[i] = num_b[i] - num_a[i] + 10;
num_b[i+1]--;
}
}

}

if (n<0) //按要求打印
printf("-");
for (i=k-1; i>=0; i--)
{
if (num_c[i])
f = 1;
if (f || i == 0 )
printf("%d",num_c[i]);
}
printf("\n");
for (i=0;i<k;i++) //清0. 进行下一次操作
{
num_a[i] = 0;
num_b[i] = 0;
}
}

return 0;

}

四 大数乘法。

大数乘法,相对之前的加法和减法,难度有所提高,但是本质还是一样的。

下面说说我的方法:

1、利用字符数组读入大数a,b

2、将大数反向存储到整型数组中。(此时满足低位在数组下标小的位置上)

3、逐个相乘。   此时要注意 乘数i位和乘数j位的乘积,应累加在结果数组的i+j位上。  这个结论不难发现,可通过列个简单的竖式乘法验证。

4.、处理进位,(从低位开始到最高位逐位处理,将本位结果的个位作为该为的结果,而10位以上的数均作为进位进到上一位,一直到所有进位处理完)

5、然后整体再反向存入字符数组,打印出结果。

 

思路很常规,算法也比较简单,但是效率方面,可能不太理想。

水平有限,只能写出这样的代码。以后有能力了,再优化优化。



#include<stdio.h>
#include<string.h>
#define MaxLen 1000
int main()
{
char str_a[MaxLen], str_b[MaxLen], str_c[2*MaxLen];
int num_a[MaxLen], num_b[MaxLen], num_c[2*MaxLen];
int i, j, k, d, len_a, len_b;

while (scanf("%s%s",str_a,str_b)!=EOF) //便于多次测试。
{
for (i=0; i<MaxLen; i++) //初始化,清0
{
num_a[i] = 0;
num_b[i] = 0;
}
for (i=0; i<2*MaxLen; i++)
num_c[i] = 0;
len_a = strlen(str_a); //颠倒存储a,b两大数
i = len_a - 1;
k = 0;
while ( i>=0 )
num_a[k++] = str_a[i--] - '0';

len_b = strlen(str_b);
i = len_b - 1;
k = 0;
while ( i>=0 )
num_b[k++] = str_b[i--] - '0';

for ( i=0; i<len_a; i++ ) //先不考虑进位,对应加到结果数组num_c中
for ( j=0; j<len_b; j++ )
num_c[i+j] += num_a[i] * num_b[j];

k = 2 * MaxLen - 1;
while ( k>=0 && num_c[k]==0 ) //寻找最高位
k--;

i = 0;
d = 0;
while( i<=k ) //处理进位
{
num_c[i] += d; //加上对应位置的进位
d = num_c[i] / 10; //得到进位
num_c[i] %= 10; //得到对应位置结果
i++;
}

while ( d>0 ) //处理最高位进位
{
num_c[i] = d % 10;
d = d / 10;
i++;
}

k = i; //得到结果的最高位
for ( i=k-1; i>=0; i-- )
str_c[k-i-1] = num_c[i] + '0'; //结果转换成字符
str_c[k] = '\0';

printf("%s\n",str_c); //结果转换成字符串
}
return 0;

}

五 大数除法。

 

大数除法,应该算是四则运算里面最难的一种了。不同于一般的模拟,除法操作步数模仿手工除法,而是利用减法操作实现的。

其基本思想是反复做除法,看从被除数里面最多能减去多少个除数,商就是多少。

逐个减显然太慢,要判断一次最多能减少多少个整的10的n次方。

以7546除23为例。

先减去23的100倍,就是2300,可以减3次,余下646。   此时商就是300;

然后646减去23的10倍,就是230,可以减2次,余下186。此时商就是320;

然后186减去23,可以减8次,此时商就是328.

 

根据这个思想,不难写出下面的代码。

还是那句话,可能算法效率不是很高。但是常规解题思路一般就是这样了。

如果以后有能力,有时间了。  我会试着去优化。


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxLen 200
//函数SubStract功能:
//用长度为len1的大整数p1减去长度为len2的大整数p2
// 结果存在p1中,返回值代表结果的长度
//不够减 返回-1 正好够 返回0
int SubStract( int *p1, int *p2, int len1, int len2 )
{
int i;
if( len1 < len2 )
return -1;
if( len1 == len2 )
{ //判断p1 > p2
for( i=len1-1; i>=0; i-- )
{
if( p1[i] > p2[i] ) //若大,则满足条件,可做减法
break;
else if( p1[i] < p2[i] ) //否则返回-1
return -1;
}
}
for( i=0; i<=len1-1; i++ ) //从低位开始做减法
{
p1[i] -= p2[i];
if( p1[i] < 0 ) //若p1<0,则需要借位
{
p1[i] += 10; //借1当10
p1[i+1]--; //高位减1
}
}
for( i=len1-1; i>=0; i-- ) //查找结果的最高位
if( p1[i] ) //最高位第一个不为0
return (i+1); //得到位数并返回
return 0; //两数相等的时候返回0
}
int main()
{
int n, k, i, j; //n:测试数据组数
int len1, len2; //大数位数
int nTimes; //两大数相差位数
int nTemp; //Subtract函数返回值
int num_a[MaxLen]; //被除数
int num_b[MaxLen]; //除数
int num_c[MaxLen]; //商
char str1[MaxLen + 1]; //读入的第一个大数
char str2[MaxLen + 1]; //读入的第二个大数

scanf("%d",&n);
while ( n-->0 )
{
scanf("%s", str1); //以字符串形式读入大数
scanf("%s", str2);

for ( i=0; i<MaxLen; i++ ) //初始化清零操作
{
num_a[i] = 0;
num_b[i] = 0;
num_c[i] = 0;
}

len1 = strlen(str1); //获得大数的位数
len2 = strlen(str2);

for( j=0, i=len1-1; i>=0; j++, i-- )
num_a[j] = str1[i] - '0'; //将字符串转换成对应的整数,颠倒存储
for( j=0, i=len2-1; i>=0; j++, i-- )
num_b[j] = str2[i] - '0';

if( len1 < len2 ) //如果被除数小于除数,结果为0
{
printf("0\n");
continue; //利用continue直接跳出本次循环。 进入下一组测试
}
nTimes = len1 - len2; //相差位数
for ( i=len1-1; i>=0; i-- ) //将除数扩大,使得除数和被除数位数相等
{
if ( i>=nTimes )
num_b[i] = num_b[i-nTimes];
else //低位置0
num_b[i] = 0;
}
len2 = len1;
for( j=0; j<=nTimes; j++ ) //重复调用,同时记录减成功的次数,即为商
{
while((nTemp = SubStract(num_a,num_b + j,len1,len2 - j)) >= 0)
{
len1 = nTemp; //结果长度
num_c[nTimes-j]++;//每成功减一次,将商的相应位加1
}
}

//输出结果
for( i=MaxLen-1; num_c[i]==0 && i>=0; i-- );//跳过高位0
if( i>=0 )
for( ; i>=0; i-- )
printf("%d", num_c[i]);
else
printf("0");
printf("\n");
}
return 0;
}