/**/ /*

    标题：< <系统设计师> >应试编程实例-[递推算法程序设计]

    作者：成晓旭

    时间：2002年09月14日(18:20:00-20:18:00)

          实现“装箱”问题的贪婪算法实现函数

    时间：2002年09月14日(22:00:00-23:18:00)

          实现“装箱”问题的贪婪算法实现函数

    时间：2002年09月14日(18:20:38-22:18:00)

          实现“人民币找零”问题的贪婪法解决算法

*/

#include     " stdio.h "

#include     " stdlib.h "

// :============================“马的遍历”问题的贪婪法解决算法===========================

int         delta_i[]  =   ... {

2,1,-1,-2,-2,-1,1,2} ;

int         delta_j[]  =   ... {

1,2,2,1,-1,-2,-2,-1} ;

int         board[ 8 ][ 8 ];         // 棋盘数组(board[i,j]表示:马经过位置[i行,j列]时的步骤)

// 求(i,j)的出口数,和各出口号于array[],start是顺序选择着法的开始序号

int         Exit_Number( int     i, int  j, int  start, int  array[])

... {

    int a,b,k,count;

    for(count = k = 0;k < 8;k++)

    ...{

        a = i + delta_i[(start + k) % 8];

        b = j + delta_j[(start + k) % 8];

        if((a >= 0 && a < 8) && (b >= 0 && b < 8) && board[a][b] == 0)

            array[count ++ ] = (start + k) % 8;

    }

    return(count);        //返回出口数

}

// 选下一出口,start是顺序选择着法的开始序号

int         Select_NextExit( int  i, int  j, int  start)

... {

    int    min_nexit,nexit,temp,a[8],b[8],k,result;

    nexit = Exit_Number(i,j,start,a);    //确定(i,j)的出口个数

    if(nexit == 0)

        return(-1);        //没有出口

    for(min_nexit = 9,k = 0;k < nexit;k++)

    ...{

//逐一考察各个出口

        temp = Exit_Number(i + delta_i[a[k]],j + delta_j[a[k]],start,b);

        if(temp < min_nexit)

        ...{

            min_nexit = temp;

            result = a[k];

        }

    }

    return(result);

}

// “马的遍历”问题主函数

void         Journey_Horse()

... {

    int x,y,i,j,start,step = 0,order;

    for(x = 0;x < 8;x ++)

    ...{

        for(y = 0;y < 8;y ++)

        ...{

            start = 0;    //从0号着法开始顺序检查

            do

            ...{

                for(i = 0;i < 8;i++)

                    for(j = 0;j < 8;j++)

                        board[i][j] = 0;        //清棋盘

                board[x][y] = 1;

                i = x;

                j = y;

                for(step = 2;step <= 64;step++)

                ...{

                    if((order = Select_NextExit(i,j,start)) == -1)

                        break;    //没有出口

                    i = i + delta_i[order];    //前进一步    

                    j = j + delta_j[order];

                    board[i][j] = step;        //马在第step步时将经过位置[i行,j列]

                }

                if(step > 64)

                    break;        //走出棋盘了,自然应该结束循环

                start ++;        //最先检查的着法序号增1

            }while(step <= 64);

            //显示当前着法的结果

            printf("x-start = [%d],y-start = [%d],start = [%d]： ",x,y,start);

            for(i = 0;i < 8;i++)

            ...{

                for(j = 0;j < 8;j++)

                    printf("%4d",board[i][j]);

                printf(" ");

            }

            scanf("%*c");        //输入回车,找下一个起点的解

        }

    }

}

// :============================“马的遍历”问题的贪婪法解决算法===========================

int  main( int  argc,  char *  argv[])

... {

    //Encase_Box();

    //Journey_Horse();

    Run_Give_Change();

    printf(" 应用程序运行结束！ ");

    return 0;

}