查看完整版本: 程序设计中的数学方法

程序设计中的数学方法

[size=3]程序设计中的数学方法[/size][size=3]程序设计中可采用多种数学方法，恰如其分的数学方法可以大大减少程序运行的时间和所需空间，起到优化程序的作用。遇到一道题目时,如进制运算,多项式运算等,应不急于马上用递归,回溯等算法,无妨先用笔算,从中发现一些规律.但是也不是每一道题都可以用数学方法完成,数学方法只能用于一些求总数,最值之类的题目上.[/size][b][color=black][font=Verdana]
[size=3][举例][/size][/font][/color][/b][b]
[/b][color=black][size=3][font=Verdana]1. 砝码设计 ([/font][font=Verdana]江苏省[/font][/size][font=Verdana][size=3]队组队选拔赛)
     设有一个天平,可以用来称重.
     任务一:设计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
     输入:n,x(n为砝码个数,x是在称出最大重量范围内的重量)
     输出:砝码方案,称出x的方案.
     输入样例1:2,2          输入样例2:2,4
     输出样例1:1,3          输出样例2:1,3
            2+1:3                  4:1+3                [/size][/font][/color]
[size=3][font=Verdana][color=black]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后,屏幕输出再用一个数组来处理就行了.[/color][/font]
[font=Verdana][color=black]3. 示范程序[/color][/font]
[/size][size=3][font=Verdana][color=black]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.[/color][/font]
[b][color=black][font=Verdana][总结][/font][/color][/b][/size][font=Verdana]
[size=3]     数学方法的合理运用,可以给编程带来很大方便,现在一些省市的信息学竞赛题,越来越多的用到数学推导.在竞赛中要取得好成绩,坚实的数学基础是很重要的.[/size][/font]

谢谢,支持.

该顶就要顶

有一个迷路的人正向对面走来的一位路人问路道：“对不起！请问这儿是哪里？”
“你现在正在一条分岔路上，”路人说。
“先生，我猜你一定是从事IT的。”迷路人道。
“对啊！你为什么会知道？”
“你[url=http://www.01809.com/]下载试题[/url]，给不出答案，完全没有用”
“先生，我也猜猜你的职业吧！你一定是做[url=http://www.40450.com/]管理[/url]的。”路人说。 “你不知自己在哪？也不知自己应往哪儿走，但你却希望我帮你解决问题，你现在的处境和先前没有两样，但责任已归咎在我身上！”