9个点一笔画的算法求解，送下100分

9个点一笔画的算法求解，送上100分
差不多一年没登过csdn了，偶尔也只是登着下载文档，在公司基本天天写lua ，写bat等等的脚本，c++也接触甚少，更别提算法了，然今天吃饭和同事讨论起了一个算法，自己几乎忘的一干二净，在此请教下大家: 
现在有种手机解锁是9个数字键，让你一笔画完的，而后我们就开始探讨起这样一笔画有几种可能性，也算是一个图论和排列组合的东西了，动态规划也不知道怎么用了，图论也忘鸟，遂请教大神们有什么好的方法呢，效率要尽量高哦。 我想着将他改了另外一种问题： 有1到9数字的九个球，他们所有的排列组合中，满足前面的数字和后面的数字差的绝对值为1或者3或者4的排列组合有几种。 
ps：好怀念大学的时候可以自己玩玩算法，虽然是个菜鸟，但至少年轻过。  一直忠实于c++ 板块，遂继续发到这里！
[解决办法]
脑袋要烧掉了~~~
[解决办法]
看来是个排列组合问题啊
[解决办法]

引用:

假设路径是有方向性的，假设每个点只经过一次，那么算是一个排列问题，总数为：
P(9, 2) + P(9, 3) + P(9, 4) + P(9, 5) + P(9, 6) + P(9, 7) + P(9, 8) + P(9, 9)

在这两个条件的基础上，要考虑的是起点和何时经过5的问题，因为如果作为3*3的矩阵，经过5后必定需要经过一个临界点才能达到目的，比如讲‘1,2,5’后只能是3和4,这样就只剩下两个选择，因为5不可能再作为一个点，所以下面的图形只有直线和三角形，且是不包含已经过点的三角形···（有事，来不及继续分析了，只能到这了。谅解·）
[解决办法]
写程序倒是简单，遍历＋回溯就是了，1379三个连接，2468有5个连接，5有8个连接
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

//1 2 3
//4 5 6 求一笔划过所有9个键的所有方法
//7 8 9
#include <stdio.h>
int g[10][9]={
    {0,0,0,0,0,0,0,0,0},
    {2,4,5,0,0,0,0,0,0},//1
    {1,3,4,5,6,0,0,0,0},//2
    {2,5,6,0,0,0,0,0,0},//3
    {1,2,5,7,8,0,0,0,0},//4
    {1,2,3,4,6,7,8,9,0},//5
    {2,3,5,8,9,0,0,0,0},//6
    {4,5,8,0,0,0,0,0,0},//7
    {4,5,6,7,9,0,0,0,0},//8
    {5,6,8,0,0,0,0,0,0},//9 
 
};
int k,i,n;
int h[10];//记录是否划过h[1..9],history
int p[10];//记录划的顺序p[1..9],path
void go(int f,int L) {
    int j;

    if (L==9) {
        p[L]=f;
        n++;
        printf("%08d:",n);
        for (i=1;i<=9;i++) printf(" %d",p[i]);
        printf("\n");
    } else {
        p[L]=f;
        h[f]=1;
        j=0;
        while (1) {
            if (g[f][j]==0) break;
            if (h[g[f][j]]==0) {
                go(g[f][j],L+1);
                h[g[f][j]]=0;
            }
            j++;
        }
    }
}
int main() {
    n=0;
    for (k=1;k<=9;k++) {
        for (i=1;i<=9;i++) h[i]=0;
        go(k,1);
    }
    return 0;
}
//00000001: 1 2 3 5 4 7 8 6 9
//00000002: 1 2 3 5 4 7 8 9 6
//00000003: 1 2 3 5 6 9 8 4 7
//00000004: 1 2 3 5 6 9 8 7 4
//00000005: 1 2 3 5 7 4 8 6 9
//00000006: 1 2 3 5 7 4 8 9 6
//00000007: 1 2 3 5 9 6 8 4 7
//00000008: 1 2 3 5 9 6 8 7 4
//00000009: 1 2 3 6 5 4 7 8 9
//00000010: 1 2 3 6 5 7 4 8 9
//00000011: 1 2 3 6 5 9 8 4 7
//00000012: 1 2 3 6 5 9 8 7 4
//00000013: 1 2 3 6 8 4 7 5 9
//00000014: 1 2 3 6 8 7 4 5 9
//00000015: 1 2 3 6 8 9 5 4 7
//00000016: 1 2 3 6 8 9 5 7 4
//00000017: 1 2 3 6 9 5 4 7 8
//00000018: 1 2 3 6 9 5 4 8 7
//00000019: 1 2 3 6 9 5 7 4 8
//00000020: 1 2 3 6 9 5 7 8 4
//00000021: 1 2 3 6 9 5 8 4 7
//00000022: 1 2 3 6 9 5 8 7 4
//00000023: 1 2 3 6 9 8 4 5 7
//00000024: 1 2 3 6 9 8 4 7 5
//00000025: 1 2 3 6 9 8 5 4 7
//00000026: 1 2 3 6 9 8 5 7 4 
 
//00000027: 1 2 3 6 9 8 7 4 5
//00000028: 1 2 3 6 9 8 7 5 4
//00000029: 1 2 4 5 3 6 9 8 7
//00000030: 1 2 4 5 7 8 9 6 3
//00000031: 1 2 4 7 5 3 6 8 9
//00000032: 1 2 4 7 5 3 6 9 8
//00000033: 1 2 4 7 5 8 9 6 3
//00000034: 1 2 4 7 5 9 8 6 3
//00000035: 1 2 4 7 8 5 3 6 9
//00000036: 1 2 4 7 8 5 9 6 3
//00000037: 1 2 4 7 8 6 3 5 9
//00000038: 1 2 4 7 8 6 9 5 3
//00000039: 1 2 4 7 8 9 5 3 6
//00000040: 1 2 4 7 8 9 5 6 3
//00000041: 1 2 4 7 8 9 6 3 5
//00000042: 1 2 4 7 8 9 6 5 3
//00000043: 1 2 4 8 7 5 3 6 9
//00000044: 1 2 4 8 7 5 9 6 3
//00000045: 1 2 4 8 9 6 3 5 7
//00000046: 1 2 5 3 6 9 8 4 7
//00000047: 1 2 5 3 6 9 8 7 4
//00000048: 1 2 5 4 7 8 9 6 3
//00000049: 1 2 5 7 4 8 9 6 3
//00000050: 1 2 6 3 5 4 7 8 9
//00000051: 1 2 6 3 5 7 4 8 9
//00000052: 1 2 6 3 5 9 8 4 7
//00000053: 1 2 6 3 5 9 8 7 4
//00000054: 1 2 6 9 8 4 7 5 3
//00000055: 1 2 6 9 8 7 4 5 3
//00000056: 1 4 2 3 5 6 9 8 7
//... ...
//00000776: 9 8 7 4 5 6 3 2 1
//00000777: 9 8 7 5 1 4 2 3 6
//00000778: 9 8 7 5 1 4 2 6 3
//00000779: 9 8 7 5 3 6 2 1 4
//00000780: 9 8 7 5 3 6 2 4 1
//00000781: 9 8 7 5 4 1 2 3 6
//00000782: 9 8 7 5 4 1 2 6 3
//00000783: 9 8 7 5 6 3 2 1 4
//00000784: 9 8 7 5 6 3 2 4 1

查看更多 下一篇