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


高一数学基础计算题

高一数学基础计算题_数学_高中教育_教育专区。高一数学计算能力基础差的不二选择。。。西江中学高一级数学周末练习系列 初中计算题(一) 班级___ 姓名___ 一、填空...

高一数学基本算法语句5

高一数学基本算法语句5_从业资格考试_资格考试/认证_教育专区。(第 6 课时)§1.3 基本算法语句 ——赋值、输入、输出语句教学目标:(1)正确理解赋值语句、输入...

苏教版高一数学基本算法语句1

苏教版高一数学基本算法语句1_从业资格考试_资格考试/认证_教育专区。第五课时 基本算法语句(一) 教学目标: 通过伪代码学习基本的算法语句,更好地了解算法思想. ...

计算能力是一项基本的数学能力

计算能力是一项基本的数学能力, 是一种复杂的智力活动, 也是学生综合能力的具体体 现。培养小学生的计算能力,是小学数学教学的一项重要任务,它不仅与数学基础知识...

初中数学基本运算能力练习 1

初中数学基本运算能力练习 1_初三数学_数学_初中教育_教育专区。初中数学基本运算能力训练(1) 2 ? 1? ?1? 1.计算: ? ? ? ? ? ? ? ? 1 ? 3 。【...

高一数学基本算法语句复习

高一数学基本算法语句复习_从业资格考试_资格考试/认证_教育专区。第 11 课时 基本算法语句复习教学目标 (1)进一步巩固基本算法语句:赋值语句、输入输出语句、条件...

高一数学基本算法语句6

高一数学基本算法语句6_从业资格考试_资格考试/认证_教育专区。基本算法语句(第 1 课时)珠海北大附属实验学校 何莲姣 教学目标:通过实例,使学生理解 3 种基本的...

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

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

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

(0838)《计算机数学基础》大作业A (1)_工学_高等教育_教育专区。西南大学网络...4. 请给出“函数 f ( x) 不定积分”的含义,并计算 xe dx . 5. 请给...

七年级数学上册基本计算题练习 (300)

七年级数学上册基本计算题练习 (300)_数学_初中教育_教育专区。七年级数学上册...(-1)= (+8.2)+(-0.6)= (+6.9)-(-0.3)= (+98)÷(-7)= (+...