| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6975 人关注过本帖, 1 人收藏
标题:九宫格(基于安卓手机锁)九个点都连的时候有几种连法(递归实现)自己写的 ...
取消只看楼主 加入收藏
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
有改了一个小bug

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<conio.h>


                                                            //        ______        //
                                                            //                    //
                                                            //     定义全局变量    //
                                                            //                    //
                                                            //        ~~~~~~        //

//记忆哪个位置放了结点的数组
int record[3][3]={0};

//计数(有多少种情况)变量
int count=0;

//记录待放入的结点的前一个结点的坐标(通过函数查找后暂时放在这里)
int iBefTemp=-1,jBefTemp=-1;




                                                            //        ______        //
                                                            //                    //
                                                            //        主函数        //
                                                            //                    //
                                                            //        ~~~~~~        //

int main()
{
    //函数声明
    void befNodePos(int n);
    int checkLine(int i);
    int checkList(int j);
    int checkCorner(int i,int j);
    void print(int a[3][3]);
    int ifCanPut(int i,int j,int n);
    int askIfPrint();
    void putInTurn(int n,int sumNum,int ifPrint);

    //主函数中的变量定义
    int i,sumSolution=0;
    int rememberPrint;

    //确定是否进行打印所有情况
    rememberPrint=askIfPrint();

    for(i=2;i<=9;i++)
    {
        putInTurn(1,i,rememberPrint);
        sumSolution+=count;
        printf("\t当连接%d个点时候有%d种连法\n\t\t累计至此有%d种连法\n\n\n",i,count,sumSolution);   
        count=0;
    }
    printf("\n\n所以,总共有%d种可能的连接方法。\n\n\n",sumSolution);

    return 0;
}



                                                            //        ______        //
                                                            //                    //
                                                            //     其他函数定义    //
                                                            //                    //
                                                            //        ~~~~~~        //

//找到前一个结点的坐标并将坐标值放置在全局变量iBefTemp和jBefTemp里
void befNodePos(int n)
{
    int i,j;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            if(record[i][j]==n-1)
            {
                iBefTemp=i;
                jBefTemp=j;
                return;
            }

        }

    }

}

//判断间隔位置是否有结点放置。(横向判断)
int checkLine(int i)
{
    if(record[i][1]==0)
        return 0;
    else
        return 1;
}

//判断间隔位置是否有结点放置。(纵向判断)
int checkList(int j)
{
    if(record[1][j]==0)
        return 0;
    else
        return 1;
}

//判断ij位置是否为顶角位置
int checkCorner(int i,int j)
{
    if(i+j==2&&i!=j||i+j==0||i+j==4)
        return 1;
    else
        return 0;
}

//打印的函数
void print(int a[3][3])
{
    int i,j;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            printf("%3d",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    getch();
}

//询问是否打印所有情况
int askIfPrint()
{
    int boo;
    printf("\n\n\t\t\t九宫格锁屏程序\n\n");
    printf("你是否想知道每一次的具体连法:\n");
    printf("1.是的,我想看看具体是怎么连的。(提示:情况非常之多)\n");
    printf("2.不,我不必知道具体都是怎么连的,我只想知道有多少种情况。\n\t\t我选择:");

    scanf("%d",&boo);

    if(boo==1)
        return 1;
    else
        return 0;
}


                                                            //        _________________        //
                                                            //                                //
                                                            //        判断能否放在ij位置        //
                                                            //                                //
                                                            //        ~~~~~~~~~~~~~~~~~~        //

int ifCanPut(int i,int j,int n)
{
    //如果这个位置还没有放置结点
    if(record[i][j]==0)
    {
        //找到前一个结点的坐标放在全局变量里面
        //如果是在放置第一个结点,则不必找它的前一个结点,任何一个位置都是合适的。
        if(n==1)
        {
            //因为是放置第一个结点,所以不必判断它跟前一个结点的关系
            return 1;
        }

        //放置除了第一个结点之外的结点,需要判断它个前一个结点的关系。
        else if(n<=9)
        {   
            iBefTemp=-1;
            jBefTemp=-1;
            befNodePos(n);

            //当中间有间隔位置时(横向判断)。
            if(i==iBefTemp&&abs(j-jBefTemp)==2)
            {
                //判断间隔位置是否有结点放置。
                if(checkLine(i))
                {
                    //已经有结点
                    //////////////可以放置........
                    return 1;
                }
                else
                {
                    //没有结点放置
                    ///////////////不能放置在ij这里
                    return 0;
                }

            }

            //当中间有间隔位置时(纵向判断)。
            else if(j==jBefTemp&&abs(i-iBefTemp)==2)
            {
                //判断间隔位置是否有结点放置。
                if(checkList(j))
                {
                    //已经有结点
                    //可以放置.............
                    return 1;
                }
                else
                {
                    //没有结点
                    //////////////不能放置在ij这里
                    return 0;
                }

            }

            //当二者为对角关系时
            else if(checkCorner(i,j)&&checkCorner(iBefTemp,jBefTemp)&&(i!=iBefTemp&&j!=jBefTemp))
            {
                //判断中间位置是否有结点放置。
                if(record[1][1]!=0)
                {
                    //中间位置已经放置了结点
                    //可以放置在ij......
                    return 1;
                }
                else
                {
                    //中间位置没有放置结点,不能放置在ij
                    return 0;
                }   

            }

            //二者中间没有间隔位置,从而可以直接放置。
            else
            {
                //可以放置...........
                return 1;
            }
        }
    }

    //如果这个位置已经放置了结点,不能放置结点
    else
    {
        return 0;
    }
   
}





                                
                                                            //        ______        //
                                                            //                    //
                                                            //        主算法        //
                                                            //                    //
                                                            //        ~~~~~~        //

void putInTurn(int n,int sumNum,int ifPrint)
{
    int i,j;

    if(n==sumNum+1)
    {
        //已经放置完9个结点,进行计数。
        count++;
        if(ifPrint)
        {
            print(record);
        }

        return;
    }

    //尝试将其放置在i行j列。
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            if(ifCanPut(i,j,n))
            {
                record[i][j]=n;
                putInTurn(n+1,sumNum,ifPrint);

                //这个语句很重要!这是递归能否进行的决定性语句。
                record[i][j]=0;
            }

        }

    }

}

欢迎批评指正。

学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2013-06-08 00:05
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
回复 16楼 seek_liu
我看这位朋友需要再思考一下您的建议。。。

学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2013-06-09 22:17
快速回复:九宫格(基于安卓手机锁)九个点都连的时候有几种连法(递归实现)自己 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026561 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved