[一.数学方法简介]
程序设计中可采用多种数学方法，恰如其分的数学方法可以大大减少程序运行的时间和所需空间，起到优化程序的作用。遇到一道题目时,如进制运算,多项式运算等,应不急于马上用递归,回溯等算法,无妨先用笔算,从中发现一些规律.但是也不是每一道题都可以用数学方法完成,数学方法只能用于一些求总数,最值之类的题目上。
[二.举例]
1. 砝码设计 (江苏省队组队选拔赛)
设有一个天平,可以用来称重.
任务一:设计n个砝码的重量,用他们能称出尽可能多的整数重量.例如,n=2,设计2个砝码的重量分别为1和3, 可称重为1,2,3,4的连续重量.
任务二:在给出n个砝码能称出最大重量范围的一重量x,试给出称出x的方案.
在上例中:
给出x=2称出的方案为2+1:3
x=4称出的方案为4:1+3
x=1称出的方案为1:1
CODE: [Copy to clipboard]
输入:n,x(n为砝码个数,x是在称出最大重量范围内的重量)
输出:砝码方案,称出x的方案.
输入样例1:2,2 输入样例2:2,4
输出样例1:1,3 输出样例2:1,3
2+1:3 4:1+3
2. 思路分析
由题目任务一可知:n=2时砝码重量最优解为1,3. 我们可以试n=3,n=4...的情况,不难发现砝码的重量均为3的1至n次方,由于理论推导涉及到累加等数学知识,我们着重看任务二。
任务二要求输出用砝码称出重为x的重量,实际上就是用3的1至n次方的和差来表示x,如样例中的2=3-1,4=1+3等,不难发现,当x除以3余1时,必然x要表示为x=a1+a2...+1,余2时x=a1+a2...-1,余0时不用1的砝码.因此取x除以3的余数,可以确定砝码1用不用和用在天平的哪一边.同理,判断3的砝码位置时,可先将x先除以3四舍五入,再除以3取余判断.能用3的1至n次方的和差来表示x后,屏幕输出再用一个数组来处理就行了。
3. 示范程序
CODE: [Copy to clipboard]
program fdsa;
uses crt,dos;
var
x,a,b,c,m,n,i,j,k:longint;
t1,t2:integer;
ch1,ch2:array [1..10] of integer;
begin
clrscr;
write('PLEASE INPUT N : '); readln(n);
write('PLEASE INPUT X : '); readln(x);
m:=x; a:=1; write(a); a:=3;
for i:=1 to n-1 do
begin
write(', ',a); a:=a*3;
end;
t1:=0; t2:=0; j:=1;
repeat
b:=x mod 3;
x:=round(x/3);
if b=2 then begin t1:=t1+1; ch1[t1]:=j; end;
if b=1 then begin t2:=t2+1; ch2[t2]:=j; end;
j:=j*3;
until x=0;
writeln;
write(m,' ');
for i:=1 to t1 do
write('+ ',ch1,' ');
write(': ');
write(ch2[1]);
for i:=2 to t2 do
write('+ ',ch2);
end.
[三.总结]
数学方法的合理运用,可以给编程带来很大方便,现在一些省市的信息学竞赛题,越来越多的用到数学推导.在竞赛中要取得好成绩,坚实的数学基础是很重要的。
