请老师指点 C语言的35课课后题第一题的递归思路

wow7jiao

http://bbs.fishc.org/thread-79184-1-4.html 原帖地址


01.#include <stdio.h>

02.

03.#define MAX_NUM 64

04.

05.int schedule[MAX_NUM+1][MAX_NUM+1];

06.

07.int arrange(int begin, int num);

08.

09.int arrange(int begin, int num)

10.{

11.        int i, j;

12.

13.        if (num == 2)

14.        {

15.                schedule[begin][1] = begin;

16.                schedule[begin][2] = begin + 1;

17.                schedule[begin+1][1] = begin + 1;

18.                schedule[begin+1][2] = begin;

19.                return 0;

20.        }

21.

22.        arrange(begin, num/2); <----我输入8个队伍，这里begin=1，num/2=4

23.        arrange(begin + num/2, num/2);<----这里是不是being=1+8/2=5，num/2=8/2=4

24.

25.        for (i = begin + num/2; i < begin + num; i++)

26.        {

27.                for (j = num/2 + 1; j <= num; j++)

28.                {

29.                        schedule[j] = schedule[i-num/2][j-num/2];

30.                }

31.        }

32.

33.        for (i = begin; i < begin + num/2; i++)

34.        {

35.                for (j = num/2 + 1; j <= num; j++)

36.                {

37.                        schedule[j] = schedule[i+num/2][j-num/2];

38.                }

39.        }

40.}

41.

42.int main(void)

43.{

44.        int num, i, j;

45.

46.        printf("请输入参赛的队伍数量：");

47.        scanf("%d", &num);

48.

49.        // 检查num是否2的N次方

50.        // 注意，这里是&，不是&&

51.        // &是按位与操作，1&1==1，0&1==0，0&0 == 0

52.        if (num & num - 1)

53.        {

54.                printf("参数队伍的数量必须是2的N次方！\n");

55.                return -1;

56.        }

57.

58.        arrange(1, num);

59.

60.        printf("编 号");

61.

62.        for (i = 1; i < num; i++)

63.        {

64.                printf("\t第%d天", i);

65.        }

66.

67.        putchar('\n');

68.

69.        for (i = 1; i <= num; i++)

70.        {

71.                for (j = 1; j <= num; j++)

72.                {

73.                        printf("%3d\t", schedule[j]);

74.                }

75.                putchar('\n');

76.        }

77.

78.        return 0;

79.}

wow7jiao

如图递归应该这样的。

22.        arrange(begin, num/2);
23.        arrange(begin + num/2, num/2
2个递归的嵌套请问流程是怎么样的？

DadingVIP

楼主可以在用IDE编程时进行debug，观察call stack调用栈的使用情况

wow7jiao

void draw(int i,int j){
printf("%d%d\n",i,j);
        if(j==2){
}
        else{
                draw(i,j/2);
                draw(i/2+k,j/2);
}
}
i,j随便等于一个值，开始执行程序，当j不等于2时，执行else中的draw(i,j/2);
就是递归开始，直到j等于2，开始返回函数，再执行else中的draw(i/2+k,j/2);
递归又开始，直到j等于2，开始返回函数。。。大概是这个流程。

wow7jiao

arrange(begin, num/2);
schedule[1][1] = 1, shchdule[1][2] = 2
schedule[2][1] = 2, shchdule[2][2] = 1

arrange(begin + num/2, num/2);
schedule[3][1] = 3, shchdule[3][2] = 4
schedule[4][1] = 4, shchdule[4][2] = 3
//这是双递归最后退出时的结果，下面的2个for循环应该是最先填充。

wow7jiao

2个for 循环是平行的，可以前后调换
--------------------------------------------------------
arrange(begin,num/2);
num = 8

for(i = 1; i < 5; i++)
     for(j = 5; j <= 8; j++)
           schedule[1][5] = schedule[5][1]
                       [1][6] =              [5][2]
                       [1][7] =              [5][3]
                       [1][8] =              [5][4]  
                       [2][5] =              [6][1]
                       [2][6] =              [6][2]
                       [2][7] =              [6][3]
                       [2][8] =              [6][4]
                       [3][5] =              [7][1]
                       [3][6] =              [7][2]
                       [3][7] =              [7][3]
                       [3][8] =              [7][4]      
                       [4][5] =              [8][1]
                       [4][6] =              [8][2]
                       [4][7] =              [8][3]
                       [4][8] =              [8][4]                    
                              


----------------------------------------------------------
arrange(begin + num/2, num/2);
num = 8

for(i = 5, i < 9; i++)
                for(j = 5; j <= 8; j++)
                        schedule[5][5] = schedule[1][1]
                        schedule[5][6] = schedule[1][2]
                        schedule[5][7] = schedule[1][3]
                        schedule[5][8] = schedule[1][4]
                        schedule[6][5] = schedule[2][1]
                        schedule[6][6] = schedule[2][2]
                        schedule[6][7] = schedule[2][3]
                        schedule[6][8] = schedule[2][4]
                        schedule[7][5] = schedule[3][1]
                        schedule[7][6] = schedule[3][2]
                        schedule[7][7] = schedule[3][3]
                        schedule[7][8] = schedule[3][4]
                        schedule[8][5] = schedule[4][1]
                        schedule[8][6] = schedule[4][2]
                        schedule[8][7] = schedule[4][3]
                        schedule[8][8] = schedule[4][4]

wow7jiao

这是顺序