注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

潘凌云的博客

简单的我 快乐的教学 快乐的生活

 
 
 

日志

 
 

归纳法和数组下标的变化  

2010-10-01 22:00:34|  分类: 奥赛资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


    在对数组的操作过程中,一般都是通过对数组下标的控制来实现对整个数组的操作,而对数组下标的控制往往是由问题要求决定的,可以通过分析归纳出具体的规律来。下面通过一些实例谈谈如何控制数组下标的变化。

[ 6-1] 将一个nn列的数值方阵沿顺时针方向旋转九十度.如下所示:

   1   2   3   4   5          21  16  11   6   1

   6   7   8   9  10          22  17  12   7   2

  11  12  13  14  15          23  18  13   8   3

  16  17  18  19  20          24  19  14   9   4

  21  22  23  24  25          25  20  15  10   5

[问题分析] nn列的数值方阵的旋转可以分层进行.例如以最外一层为例,可将其看成由四条边组成的,每条边上分别有n-1个元素,如上边的元素为a[1,1],a[1,2],a[1,3],a[1,4], 旋转便是对每条边上的每个元素循环移动一次,a[1,1]a[1,n]a[n,n]a[n,1]a[1,1],经过分析,a[i,j]而言,a[i,j]a[j,n+1-i]a[n+1-i,n+1-j]a[n+1-j,i]a[i,j].每层的上边的元素构成一个倒三角形或梯形(题中阴影部分),整个方阵由四个三角形或梯形拼凑而成,程序中以倒三角形的每个元素为首元素进行循环移动.

[程序清单]

program ex6_1(input,output);

const max=20;

var i,j,n,left,right,temp:integer;

    a:array [1..max,1..max] of integer;

begin

     write('Input n:'); readln(n);

     for i:=1 to n do

     begin

          for j:=1 to n do a[i,j]:=n*(i-1)+j;

          for j:=1 to n do write(a[i,j]:4); writeln

     end;

     writeln;

     i:=1;left:=1;right:=n-1;{从第i行的第left到第right的元素为旋转对象}

     while left<=right do

     begin

          for j:=left to right do

          begin

               temp:=a[i,j];

               a[i,j]:=a[n+1-j,i];

               a[n+1-j,i]:=a[n+1-i,n+1-j];

               a[n+1-i,n+1-j]:=a[j,n+1-i];

               a[j,n+1-i]:=temp

          end;

          i:=i+1; left:=left+1; right:=right-1

     end;

     for i:=1 to n do

     begin

          for j:=1 to n do write(a[i,j]:4); writeln

     end

end.

[运行程序]下划线表示输入

Input n:6

   1   2   3   4   5   6{旋转前的矩阵}

   7   8   9  10  11  12

  13  14  15  16  17  18

  19  20  21  22  23  24

  25  26  27  28  29  30

31       32  33  34  35  36

 

  31  25  19  13   7   1{旋转后的矩阵}

  32  26  20  14   8   2

  33  27  21  15   9   3

  34  28  22  16  10   4

  35  29  23  17  11   5

  36  30  24  18  12   6

 

 [ 6-2] 生成一个螺旋方式排列自然数1,2,……,N*NN阶方阵.N=5时方阵如下:

   1   2   3   4   5

  16  17  18  19   6

  15  24  25  20   7

  14  23  22  21   8

  13  12  11  10   9

    本例可采用类似于上例方阵旋转的方法来生成螺旋方阵,所不同的是每个元素转至其下一位置时,要增加一个边长值再填入,且少转一次,不构成循环旋转.N为奇数时,方阵存在一个中心,中心元素要单独赋值.

[程序清单]

program ex6_2(input,output);

const max=20;

var i,j,k,n,left,right:integer;

    a:array [1..max,1..max] of integer;

begin

     write('Input n:'); readln(n);

     k:=0; i:=1; left:=1; right:=n-1;

     while left<=right do

     begin

          for j:=left to right do

          begin

               k:=k+1; a[i,j]:=k;

               a[j,n+1-i]:=a[i,j]+right-left+1;

               a[n+1-i,n+1-j]:=a[i,j]+2*(right-left+1);

               a[n+1-j,i]:=a[i,j]+3*(right-left+1);

          end;

          k:=k+3*(right-left+1); i:=i+1; left:=left+1; right:=right-1

     end;

     if n mod 2=1 then a[n div 2+1,n div 2+1]:=n*n;

     for i:=1 to n do

     begin

          for j:=1 to n do write(a[i,j]:4);

          if n<20 then writeln

     end

end.

[运行程序]下划线表示输入

Input n:7

   1   2   3   4   5   6   7

  24  25  26  27  28  29   8

  23  40  41  42  43  30   9

  22  39  48  49  44  31  10

  21  38  47  46  45  32  11

  20  37  36  35  34  33  12

  19  18  17  16  15  14  13

Input n:8

   1   2   3   4   5   6   7   8

  28  29  30  31  32  33  34   9

  27  48  49  50  51  52  35  10

  26  47  60  61  62  53  36  11

  25  46  59  64  63  54  37  12

  24  45  58  57  56  55  38  13

  23  44  43  42  41  40  39  14

22       21  20  19  18  17  16  15

[ 6-3] 偶数幻方

   我国古代数学家杨辉提出了由自然数方阵构造4倍阶幻方的原则:将阶数为四的倍数的棋盘,从左到右、从上到下地填上自然数1至阶数平方(8阶时为64),如图1。然后以方阵中心点为对称中心,把图1中加底纹的格子里的数与它在棋盘上的对称点上的数交换位置,得到的图2就是一种4倍阶幻方。

 1  2  3  4  5  6  7  8           1 63 62  4  5 59 58  8

 9 10 11 12 13 14 15 16             56 10 11 53 52 14 15 49

17 18 19 20 21 22 23 24             48 18 19 45 44 22 23 41

25 26 27 28 29 30 31 32             25 39 38 28 29 35 34 32

33 34 35 36 37 38 39 40             33 31 30 36 37 27 26 40

41 42 43 44 45 46 47 48             24 42 43 21 20 46 47 17

49 50 51 52 53 54 55 56             16 50 51 13 12 54 55  9

57 58 59 60 61 62 63 64             57  7  6 60 61  3  2 64

      (图1                               (图2

    要求对输入的自然数NN不超过20,且是4的倍数),输出N幻方。输出不超过一屏,且要如图2一样对齐。

[算法设计] 通过观察可以发现需要交换位置的每对元素的行数和列数和均为n+1,且一个处于上半部分(1N div 2行),另一个处于下半部分,因此程序只要找出上半部分的处于阴影中的数,将它们与对称位置上的数交换即可。考虑左上角4*4 的子阵,其中处于阴影中的数有八个,它们的位置记录在二维常量数组p中,经归纳,这些位置的行数与列数加上4的倍数后也是需交换数据的位置,这样就可以判断哪些位置上的数需要交换。

[程序清单]

program ex6_3(input,output);

const max=20;

const p:array[1..8,1..2] of longint

       =((1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3));

var i,j,k,n,temp:longint;

    a:array[1..max,1..max] of longint;

function active(x,y:longint):boolean;

var yes:boolean;

    k:longint;

begin

     yes:=false;

     for k:=1 to 8 do

         if (x mod 4=p[k,1] mod 4) and (y mod 4=p[k,2] mod 4)

            then yes:=true;

     active:=yes

end;

begin

     write('Input n:'); readln(n); k:=1;

     for i:=1 to n do

         for j:=1 to n do begin a[i,j]:=k; k:=k+1 end;

     for i:=1 to n div 2 do

         for j:=1 to n do

             if active(i,j) then

             begin temp:=a[i,j];a[i,j]:=a[n+1-i,n+1-j];a[n+1-i,n+1-j]:=temp end;

     for i:=1 to n do

     begin

          for j:=1 to n do write(a[i,j]:4);

          if n<20 then writeln

     end;

end.

[ 6-4] 编程输出下列形式的N*N双螺旋数字方阵,其中N≤20,输出格式要求同一列数据要对齐,总共输出N行.

N=7时                             N=8时

16  15  14  13  12  11  28     22  21  20  19  18  17  16  36

17   4   3   2  10  27  29     23   7   6   5   4  15  35  37

18   5   1   9  26  43  30     24   8   1   3  14  34  54  38

19   6   8  25  42  44  31     25   9   2  13  33  53  55  39

20   7  24  41  49  45  32     26  10  12  32  52  63  56  40

21  23  40  48  47  46  33     27  11  31  51  62  64  57  41

22  39  38  37  36  35  34     28  30  50  61  60  59  58  42

                             29  49  48  47  46  45  44  43

[问题分析]

    方阵填数是常见的问题,这个双螺旋方阵填数规则比较复杂,又有两个方向,比起简单螺旋方阵来不易用计算法实现.由于这一类问题中数从1变化到N*N的过程中,其对应的位置是有规律的,即知道了当前数的位置后,不难推出下一个数所在的位置.根据这一思路,采用递推的方法求当前位置的下一个位置的算法来解决这个问题.一般来说应该以1所在的位置作为起始位置,但在本例中, 1的位置不好确定.遇到这种情况,就应该换个思路,不从1填起.通过观察, 位于左下至右上的反对角线上的元素较有规律,在这条对角线的左上侧共有(n-1)×n/2个数.所以对角线上的数字就不难得到了.

  以往,填方阵用得比较多的是计算下标,用在这儿有点烦.可以考虑设一个方向变量表示旋转的规则.

[算法设计]

    对于方阵(数组)a,首先将(n-1)×n/2 + 1(n-1)×n/2 + n之间的自然数填到(赋给)反对角线对应的元素中.反对角线上对应元素的下标i,ji+j=n+1.

  接着填入主对角线左上侧的数.事先对于a,我们在它的外面多加一圈“围墙”,表示这些位置不可到达,以避免出界.然后便可利用方向变量d,规则为先向上,再向右,再向左下,如此循环直至填完(n-1)×n/2以内的所有自然数.

主对角线右下方,经观察有a[i,j]+a[n+1-i,n+1-j]= n×n+1,故可很方便得到.

这一算法具有通用性,如蛇形方阵和螺旋方阵的生成都可以用此算法的思想来实现,有兴趣的读者可以试着编写相关的两个程序.

程序清单:

program ex6_4(input,output);

const max=20;

var i,j,k,n,d:integer;

    a:array[0..max+1,0..max+1] of integer;

begin

     write('Input n:');

     readln(n);

     for i:=0 to n+1 do

         for j:=0 to n+1 do a[i,j]:=0;

     a[0,1]:=-1;a[n+1,n]:=-1;

     for i:=1 to n do a[n+1-i,i]:=(n-1)*n div 2+i;

     i:=n;j:=1;d:=1;

     for k:=a[i,j] downto 1 do

     begin

          a[i,j]:=k;a[n+1-i,n+1-j]:=n*n+1-k;

          case d of

          1:i:=i-1;

          2:j:=j+1;

          3:begin i:=i+1;j:=j-1 end

          end;

          if a[i,j]<>0 then

             begin

             case d of{后退一步}

             1:i:=i+1;

             2:j:=j-1;

             3:begin i:=i-1;j:=j+1 end

             end;

             d:=d+1;if d=4 then d:=1;{换下一方向}

             case d of{再前进一步}

             1:i:=i-1;

             2:j:=j+1;

             3:begin i:=i+1;j:=j-1 end

             end

             end

     end;

     for i:=1 to n do

     begin

          for j:=1 to n do write(a[i,j]:4);

          if n<20 then writeln

     end;

end.

[6-5] 回文数

       若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。

       例如:给定一个10进制数56,将5656(即把56从右向左读),得到121是一个回文数。

       又如:对于10进制数87

              STEP187+78  = 165                  STEP2165+561 = 726

              STEP3726+627 = 1353                        STEP41353+3531 = 4884

       在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884

       写一个程序,给定一个N2<=N<=10N=16)进制数M,求最少经过几步可以得到回文数。

       如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”

样例:

INPUT                                  OUTPUT

 N = 9  M= 87                           STEP=6

[算法设计] 本问题的核心是高精度加法,具体处理起来可以分为三个部分。

第一,是对读入数据的处理。本题中,数据的进制是可变的,所以用整型数(即十进制数)不是很方便,考虑一般情况,我们可以采用字符串读入,再对数据作后期加工,把它的每一位都分离开来,存入一个数组digit里,数组invert存放数组digit的倒序,变量len记录了数据的位数。在转化过程中要注意到16进制的特殊性,要对于字母A B C D E F要单独处理。

第二,进行判断与运算。存储数据时用什么形式表示其实无所谓,关键是做加法运算的时候要符合n进制的规律。所以,运算时一律以10进制形式存储,存储该位数码对应的十进制数值,A10F15表示。判断是否构成回文数时也一样用10进制,逐对比较对称的两个数位上的数字,看它们是否相等。做加法的次数以30次为限。

第三,输出结果。如果当前的数是回文数,则输出步数;否则按“Impossible”输出。

[程序清单]

program ex6_5(input,output);

const max=1000;

type arraytype=array [1..max] of longint;

var i,n,len,step:longint;

    str:string;

    digit,invert:arraytype;

function palindrome(var digit:arraytype;len:longint):boolean;

var i,j:longint;

begin

     i:=1; j:=len;

     while (i<j) and (digit[i]=digit[j]) do

     begin i:=i+1; j:=j-1 end;

     if i<j then palindrome:=false else palindrome:=true

end;

begin

     write('Input n:'); readln(n);

     write('Input number:'); readln(str);

     for i:=1 to max do digit[i]:=0;

     len:=length(str);

     for i:=1 to len do

         if str[i]>='A'

            then digit[len+1-i]:=ord(str[i])-ord('A')+10

            else digit[len+1-i]:=ord(str[i])-ord('0');

     step:=0;

     while (step<30) and not(palindrome(digit,len)) do

     begin

          for i:=1 to len do invert[i]:=digit[len+1-i];

          for i:=1 to len do digit[i]:=digit[i]+invert[i];

          for i:=1 to len do

              if digit[i]>=n then

                 begin digit[i+1]:=digit[i+1]+1;

                       digit[i]:=digit[i]-n end;

          if digit[len+1]>0 then len:=len+1;

          step:=step+1

     end;

     if step=30

        then writeln('Impossible!')

        else writeln('STEP=',step)

end.

[ 6-6] 用高精度计算出S=1+2+3++n!(n50),其中“!”表示阶乘,例如:5=5*4*3*2*1,输入正整数N,输出计算结果S

[算法设计] 本题涉及高精度加法和乘法运算,程序使用二个一维数组sf分别存储到当前项为止的和与当前项的值,计算当前项的值采用递推的迭代的方法,即k!=(k-1)*k

[程序清单]

program ex6_6(input,output);

const maxlen=100;

type arraytype=array [0..maxlen] of longint;

var i,n:integer;

    f,s:arraytype;

procedure mul(var a:arraytype; k:longint);

var i:longint;

begin

     for i:=0 to maxlen do f[i]:=f[i]*k;

     for i:=0 to maxlen-1 do

     begin

          a[i+1]:=a[i+1]+a[i] div 10;

          a[i]:=a[i] mod 10

     end

end;

procedure add(var a:arraytype;b:arraytype);

var i:longint;

begin

     for i:=0 to maxlen do a[i]:=a[i]+b[i];

     for i:=0 to maxlen-1 do

         if a[i]>=10 then

            begin

                 a[i+1]:=a[i+1]+1;

                 a[i]:=a[i]-10

            end

end;

procedure print(a:arraytype);

var i,j:longint;

begin

     i:=maxlen;

     while (i>0) and (a[i]=0) do i:=i-1;

     for j:=i downto 0 do write(a[j])

end;

begin

     write('Input n:');

     readln(n);

     for i:=0 to maxlen do s[i]:=0;

     for i:=1 to maxlen do f[i]:=0;

     f[0]:=1;

     for i:=1 to n do

     begin

          mul(f,i);

          add(s,f);

     end;

     print(s);

     writeln

end.

[ 6-7] 读入自然数mn0mn1000),判断分数m/n是有限小数还是循环小数。如果m/n是有限小数,则输出分数的值;如果m/n为循环小数,则把循环部分括在括号中打印输出。

[算法设计] 数组POS以余数作下标存放余数的位置代码(小数点以后位数的位置),数组QUOT以位置代码为下标存放商的某一位数,m/n的整数部分始终为0,所以m为第一个余数。如果m/n是有限小数,则反复进行除法运算后余数会成为0。如果m/n不是有限小数,则反复进行除法运算时,当第y次的余数与前面第x次的余数相等,也就可以确定为循环部分。循环部分为x+1位到y的部分。输出时将循环部分用括号括起来输出。

[程序清单]

program ex6_7(input,output);

const maxn=1000;

var i,m,n,r,tail:integer;

    quot,pos:array [0..maxn] of integer;

begin

     write('Input m,n(0<m<n<=1000)=');

     readln(m,n);

     for i:=0 to maxn do pos[i]:=-1;

     tail:=0; r:=m;

     while (r<>0) and (pos[r]=-1) do

     begin

          pos[r]:=tail;

          r:=10*r;

          tail:=tail+1;

          quot[tail]:=r div n;

          r:=r mod n;

     end;

     write(m,'/',n,'=0.');

     if r=0

        then for i:=1 to tail do write(quot[i])

        else begin for i:=1 to pos[r] do write(quot[i]);

                   write('(');

                   for i:=pos[r]+1 to tail do write(quot[i]);

                   write(')')

             end;

     writeln

end.

  评论这张
 
阅读(73)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018