nbhkdz.com冰点文库

基础算法(一) 数学基础


基础算法( 基础算法(一) 数学基础 一、学习要点 1.数论:素数、最大公约数、最小公倍数、整除、求余、同余、shl、shr 位运算; 2.方程与矩阵:解方程的根,矩阵的相乘; 3.进制转换; 4.高精度计算:用数组存储,考虑进位,最高位、最低位; 5.组合数学:排列、组合的生成算法,排列、组合数的计算,抽屉原理、容斥原理。 备注:同余:两个整数 a,b,若它们除以整数 m 所得

的余数相等,则称 a,b 对于 模 m 同余 。记作 a ≡ b (mod m) 读作 a 同余于 b 模 m,或读作 a 与 b 关于模 m 同 余。 比如 26 ≡ 14 (mod 12) 【定义】设m是大于 1 的正整数,a,b 是整数,如果 m|(a-b),则称 a 与 b 关于模 m 同余,记作 a≡b(mod m),读作 a 同余于 b 模 m. 二、重点提示 (1)数据范围: 类型 Integer Shortint Longint Byte Word longword Int64 Qword 整型 短整型 长整型 单字节整型 双字节整型 含义 取值范围 -32768~32767 -128~127 -2147483648 ~2147483647 0~255 0~65535 0~4294967295 -9223372036854775808~9223372036854775807 0~18446744073709551615 字节数 2 1 4 1 2 4 8 8

(2)注意事项: a.数据的输入:一律倒置,即使除法从高位开始,也倒置过来; b.数据的存储:用数组存储; c.数据的运算:进位和错位,记住进位是从低到高位, “进商存余” ; d.结果的输出:注意数组的输出顺序,小数点的位置,处理多余的 0 等。 (3)高精度加法运算 已知:a 和 b(<10240) 。计算输出:a+b 的值。 样例输入: 99 999 样例输出 1098 算法分析: 数据的输入:因为两个加数 a 和 b 最大值是 10240,考虑用字符串变量 s1、s2;
1

数据的存储:分别用数组 a、b 存储 s1、s2 两个加数,对于“和”可以用一个新的数组 c 存储,也可把“和”存储在其中一个加数的数组中; 进位处理:可以“先加再进位” ,也可以“边加边进位” ; 结果输出:因为输入时两个加数是“倒置”的,所以输出“和”时还需要再倒一次; 参考程序:a=a+b 结果存在数组 a 中,边加边进位。 Begin Readln(s1);readln(s2); Len1:=length(s1);len2:=length(s2); Fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); For i:=1 to len1 do a[i]:=ord(s1[len1-i+1])-48; For i:=1 to len2 do b[i]:=ord(s2[len2-i+1])-48; If len1>len2 then len:=len1 else len:=len2; For i:=1 to len do Begin a[1+1]:=a[i+1]+(a[i]+b[i]) div 10; a[i]:=(a[i]+b[i]) mod 10; end; if a[len+1]>0 then len:=len+1; for i:=len downto 1 do write(a[i]); end. (4)高精度减法运算 问题表述:输入 a,b(<10240)两个数,输出 a-b 的值。 样例 1 输入: 456 409 样例 1 输出: 47 样例 2 输入: 999 1000 样例输出: -1 算法分析: a.读入被减数 s1; b.读入减数 s2; c.如果 s1<s2,那么交换 s1 和 s2;(只需计算 s1-s2) d.把 s1 存到数组 a; e.把 s2 存到数组 b; f.从低到高位计算 a[i]=a[i]-b[i];注意错位; g.输出数组 a 就是计算结果。 解决的问题: a.输入、保存。 b.比较 a 和 b 的大小,从而确定结果的正负号。如果 s1>s2,不交换;如果 s1<s2,交换 s1 和 s2,保证后面 s1-s2.

2

s1<s2 的条件: if (length(s1)<length(s2)) or ((length(s1)=length(s2)) and (s1<s2)) then begin fh:=’-‘; s:=s1;s1:=s2;s2:=s; end. 然后数组 a 存 s1,b 存 s2。计算 a=a-b。 c.错位: if a[i]<b[i] then begin a[i+1]:=a[i+1]-1; a[i]:=a[i]+10; end; a[i]:=a[i]-b[i]; d.输出。 参考程序{a=a-b} Type numtype=array[1..240] of integer; Var a,b:numtype; s1,s2,s:string; la,lb,k:integer; i:integer; fh:char; begin readln(s1);readln(s2); if (length(s1)<length(s2)) or ((length(s1)=length(s2)) and (s1<s2)) then begin fh:=’-‘; s:=s1;s1:=s2;s2:=s; end; la:=length(s1);lb:=length(s2); fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); for i:=1 to la do a[i]:=ord(s1[la-i+1])-48; for i:=1 to lb do b[i]:=ord(s2[lb-i+1])-48; k:=la; for i:=1 to k do begin if a[i]<b[i] then begin a[i+1]:=a[i+1]-1; a[i]:=a[i]+10; end; a[i]:=a[i]-b[i]; end; while (a[k]=0) and (k>1) do k:=k-1;

3

if fh=’-‘ then write(fh); for i:=k downto 1 do write(a[i]); writenln; end. (5)高精度乘法运算 200 8 a.高精度乘单精度:求 a*b,a≤10 ,b≤10 . Var i,len:integer; s:string;b,m:longint; a:array[1..250] of longint; begin readln(s);readln(b);{读入被乘数 a,乘数 b} len:=length(s); for i:=1 to len do a[i]:=ord(s[len-i+1])-48; for i:=1 to len do a[i]:=a[i]*b;{每项乘 b} for i:=1 to len do {处理进位} begin a[i+1]:=a[i+1]+a[i] div 10; a[i]:=a[i] mod 10; end; m:=a[len+1]; while m<>0 do begin inc(len); a[len]:=m mod 10; m:=m div 10; end; for i:=len downto 1 do write(a[i]); end. b.高精度乘高精度 var i,j,la,lb,len:integer;s1,s2:string;m:longint; a,b,c:array[1..250] of interger; begin readln(s1);la:=length(s1); for i:=1 to la do a[i]:=ord(s[la-i+1])-48; readln(s2);lb:=length(s2); for i:=1 to lb do b[i]:=ord(s[lb-i+1])-48; for i:=1 to la do for j:=1 to lb do c[i+j-1]:=c[i+j-1]+a[i]*b[j]; len:=la+lb; for i:=1 to len do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10; end;

4

while (c[len]=0) and (len>1) do dec(len); for i:=len downto 1 do write(c[i]); end. (6)高精度除法(高精度 a 除以单精度 b,a:=a/b) Var a:array[0..300] of integer; S1,s2:string; i,len,k:integer;b,d:longint; begin readln(s1);readln(b);fillchar(a,sizeof(a),0); len:=length(s1); for i:=1 to len do a[i]:=ord(s[len-i+1])-48; d:=0; for i:=len downto 1 do begin d:=d*10+a[i];; a[i]:=d div b; d:=d mod b; end; while (len>1) and (a[len]=0) do dec(len); for i:=len downto 1 do write(a[i]); end. 2.组合数学 (1)排列的生成算法: (递归,深度优先产生) Const m=6; Var a:array[1..m] of integer;b:array[1..m] of Boolean; Procedure print; Var i:integer; Begin for i:=1 to m do write(a[i]);writeln;end; Procedure try(dep:integer);{要记住深度优先搜索的过程,并理解} Var i:integer; Begin For i:=1 to m do If b[i] then begin a[dep]:=i;b[i]:=false; if dep=m then print else try(dep+1); b[i]:=true; end; end; begin fillchar(b,sizeof(b),true); try(1); end; (2)组合的生成算法:根据前一组合产生下一组合(字典序法) Const n=6;m=4;

5

Var a:array[1..m] of integer; i,j:integer; procedure print; var i:integer; begin for i:=1 to m do write(a[i]); writeln; end; begin for i:=1 to m do a[i]:=i; repeat print; i:=m; while (i>0) and (a[i]=n-m+i) do dec(i); if i>0 then begin a[i]:=a[i]+1; for j:=i+1 to m do a[j]:=a[j-1]+1;end; until i=0; end. (3)排列组合数的计算: 主要思路有: a.根据帕斯卡恒等式 c(n,m)=c(n-1,m)+c(n-1,m-1); b.根据组合数的定义 c(n,m)=n!/(m!*(n-m)!); c.利用分解质因数方法通分。 以上几种思路都有可能要加上高精度计算。 3.进制转换 (1)将十进制转换成任意进制的数(设进制 n<10) Program dzbd; Var a:array[1..50] of interger; n,x,y,i:integer; begin write(‘input number x,y:’); read(x,y); writeln; i:=0; repeat i:=i+1; a[i]:=y mod x; y:=y div x; until y=0; for n:=i downto 1 do write(a[n]); writeln; end. (2)将任意进制数转换成十进制数

6

Program bdzd; Const m=20; Var str1:string;str2:char; n,i,l,y,t:integer; x:longint;{在数字输入时可能超过 5 位数,如:100110} a:array[1..m] of integer; begin writeln(‘input number x,n:’); readln(x,n); str(x,str1);{将数值转换成字符串} l:=length(str1); for i:=1 to l do begin str2:=str1[i]; a[i]:=ord(str2)-ord(‘0’); end; y:=1;t:=a[l]; for i:=l-1 downto 1 do begin if a[i]>n then {判断所输入数的每一位是否超出 n} begin writeln(‘error’); exit; end; y:=y*n; t:=t+a[i]*y; end; writeln(x,’ ‘t); end. 三、应用策略: “数学”一类的问题通常有比较明显的规律或公式,解题时都是紧紧抓住这些关键条 件,至于问题中涉及到的高精度计算等要求,通常都先避开,写出常规数据能过的程序之后 再通过子程序补充高精度计算。 四、例题分析: 放球 ball.bas 把 n 个球放入编号为 0,1,2,…,49 的 50 个盒子内(n<1050),使第 i 个盒子内必须放 pi*mi 个球,如果该盒无法满足这一条件,则一个也不放。其中 2≤m≤16,pi 是 0 到 m-1 之间的整 数。求出放球的具体方案。 输入文件:ball.in 有两行,第一行是 n,第二行是 m。 输出文件:ball.out 有若干行,每行一个整数,第 i 行的数表示第 i 个盒子应放的球 数。 输入样例:29 2 输出样例: 1 0 4

7

8 16 注意:输出文件中的 0 表示对应的盒子一个球都不放,如果从某个盒子开始全都不放 球,则不必输出。如上例中只需 0~4 共 5 个盒子,第六个开始都用不上,所以输出文件只 输出前 5 个盒子的方案。 解题思路与参考程序: 认真地看完题目, “第 i 个盒子内必须放 pi*mi 个球“,这一条件启发我们是把 n 转换 成 m 进制数。其中 pi 是系数。 算法步骤: (1)将 n 转换为 m 进制数,得到 yu 数组; (2)产生 m 的各次幂,得到 mi 数组; 0 50 对于不同的 n,其对应的 m 进制数位数是不同的。程序中没有直接把 m 到 m 先计算好 放在放在 mi 数组中,这样就节约了很多时间和空间。 (3)yu 和 mi 数组相乘,得到结果 result 数组。 参考程序: Var I,j,m,len,ly,lm,lr,d:integer; st:string; n:array[1..50] of word;{用 byte 就足够} yu,mi,result:array[1..20000] of word;{1..200 就足够,因为<1050,按最小的进制 (而进制化)也不超过 200 位} function sub_change:integer; {n 除 m 返回余数} var i:integer; begin d:=0; for i:=len downto 1 do begin d:=d*10+n[i]; n[i]:=d div m; d:=d mod m; end; while (len>=1) and(n[len]=0) do dec(len); exit(d); end; procedure sub_mi; {获取 m 的各次幂} var i,t:integer; begin lm:=lm+2; for i:=1 to lm do mi[i]:=mi[i]*m; for i:=1 to lm do begin mi[i+1]:=mi[i+1]+mi[i] div 10; mi[i]:=mi[i] mod 10; end; while (lm>0) and (mi[lm]=0) do dec(lm);

8

end; procedure sub_out(y:integer); {余数和幂乘积} var i,t:integer; begin fillchar(result,sizeof(result),0); result[1]:=1; lr:=lm+15; {m 最大为 16,所以余数最大为 15,乘积的长度最多加 15} for i:=1 to lm do result[i]:=mi[i]*yu[y]; for i:=1 to lr do begin result[i+1]:=result[i+1]+result[i] div 10; result[i]:=result[i] mod 10; end; while (lr>0) and (result[lr]=0) do dec(lr); for i:=lr downto 1 do write(result[i]);writeln; end; begin assign(input,'ball.in');reset(input); readln(st);readln(m);close(input); assign(output,'ball.out');rewrite(output); len:=length(st); for i:=1 to len do n[i]:=ord(st[len-i+1])-48; ly:=0; repeat {获得余数,yu 记录的是 m 进制数} inc(ly); yu[ly]:=sub_change; until len=0; fillchar(mi,sizeof(mi),0);mi[1]:=1;lm:=1; writeln(yu[1]*mi[1]); for i:=2 to ly do begin sub_mi; if yu[i]=0 then writeln(0) else sub_out(i); end; close(output); end.

9


基础算法(一) 数学基础

基础算法(一) 数学基础_数学_高中教育_教育专区。有关进制转换、高精度、排列、组合的算法基础算法( 基础算法(一) 数学基础 一、学习要点 1.数论:素数、最大公...

小学生必须背过的数学基础算法

小学生必须背过的数学基础算法_数学_小学教育_教育专区。小学生必须背过的数学基础算法,速算,提高数学能力,孩子学习教育必备 一、1-25 的平方 1×1=1 2×2=4...

RSA算法从数学基础到实例全面解1

RSA 算法数学基础到实例全面解析分类: 算法 2011-11-20 21:59 148 人阅读...4 的基础上加上模 等 但是寻找这样的 x 并不是一目了然,可以用下面的扩展...

遗传算法的数学基础

本章将较全局地介绍遗传算法的基础数学理论和分析工具,包 括验证基础遗传算法(...表示基因串中某些特征位相同的结构, 因此模式也可能解释为相同的 构形,是一个...

艺术班数学基础专题训练(16)(基础+练习+习题+复习)算法

艺术班数学基础专题训练(16)(基础+练习+习题+复习)算法_数学_高中教育_教育专区。基础知识专题训练 16 一、考试要求 内容 算法的有关概念 算法初步 流程图 基本...

基础算法(一)穷举法

基础算法( 基础算法(一)穷举法穷举法的基本思想: 穷举法的基本思想:从可能的解...穷举法解题思路: 穷举法解题思路: 对命题建立正确的数学模型; 1、 对命题建立...

四年级数学基础计算每天一练

四年级数学基础计算每天一练_数学_小学教育_教育专区。适合基础薄弱,计算能力差的学生,每天坚持做一做,运算速度逐渐提高文星教育— “教育是项良心工程” 基础计算,...

高一数学基础训练题(算法初步)

高一数学基础训练题 高一数学基础训练题 基础全国高考试题选择题(算法初步) 全国...上(右)图是一个算法的流程图,最后 输出的 W = 127 算法初步 -2- 11. ...

(0838)《计算机数学基础》大作业A (1)

西南大学网络与继续教育学院课程考试试题卷类别: 网教 专业: 计算机应用技术、计算机教育 课程名称【编号】 : 计算机数学基础 【0838】 大作业一、 大作业题目 1....