一道下海交大研究生入学考试试题：物以稀为贵

一道上海交大研究生入学考试试题：物以稀为贵
1  2  3   
4  5  6
7  8  9 
   0  
说某移动电信运营商开发了一个名为“争霸”的游戏，为鼓励用户参与，凡签约用户均可获得前三位为888的手机号码，但这样的话就有10的8次方种可能，现在给出一种限制条件减少号码数量，就是两个相邻号码之间的关系必须满足象棋里的“将步”
即：给你前三位都是888  后面8位是上面的数字  每个数的相邻只有有限个数字
比如8881*  那么与1相邻的只可以是2和4  
888812那么与2相邻的只可以是1，5，3  就是这个意思
如果选择5  那么可以选择的有2，4，6，8 
问：
1  用什么算法比较好？为什么？
2  最优的算法是什么？为什么？
3  用什么数据结构最好？为什么？
4  时间复杂度和空间复杂度？
5  一共有多少种情况？


[解决办法]
就是一个DP吧。用二维数组保存 dp[i][j]表示以i开头的，后继长度为j的i+1 位数字能够组成的号码的个数。

问题求的就是dp[8][8].转移方程就是dp[i][j]= /Sigma {dp[k][j-1]}   其中k是与i相邻的数。

复杂度的话，因为是一个确定数据，所以不太好说。如果键盘是m*n 的话，上面dp 方程的复杂度是O(4mn)的。4表示其临域是4临域，如果是八临域的话就是O(8mn),实质就是O(mn).
[解决办法]
不知道什么是最好的。
就用了个最简单的数据结构，链表。总共14826种可能，耗时0.06秒。这题是机试还是笔试？
def findNumber():
    nodeDict = {'0':('8',),
                '1':('2','4'),
                '2':('1','3','5'),
                '3':('2','6'),
                '4':('1','5','7'),
                '5':('2','4','6','8'),
                '6':('3','5','9'),
                '7':('4','8'),
                '8':('0','5','7','9'),
                '9':('6','8')}
    result = []
    nodelist = [[str(x) for x in range(0,10)]]
    current = []
    while nodelist:
        #永远取最末端的最末位一个加入数组
        current.append(nodelist[-1].pop())
        #到达8位数了没？如果没到达，往nodelist加入新的节点链
        if len(current)!=8:
            nodelist.append(list(nodeDict[current[-1]]))
        else:
            #如果到达了8位数，将数加入到输出数组
            result.append(''.join(current))
            current.pop()
        #舍掉末端搜索完毕的枝节点
        while not nodelist[-1]:
            nodelist.pop()
            if current:
                current.pop()
            else:
                break;

    return result
            
t = time.time()
result = findNumber()
print('time:',time.time()-t)
print(len(result))
[解决办法]
用不着图的遍历。一个位置上的数字出现的可能性为其邻居在前一位置出现可能性之和。

时间复杂度O(n)，n是号码的长度。空间复杂度O(1)，与号码长度无关。

#include <iostream>
using namespace std;

// 1 2 3
// 4 5 6
// 7 8 9
//   0

int a[2][10] = {{1,1,1,1,1,1,1,1,1,1}};

int main()
{
    int* src=a[0];
    int* dst=a[1];
    for( int i = 1; i < 8; ++i )
    {
        dst[0] = src[8];
        dst[1] = src[2] + src[4];
        dst[2] = src[1] + src[3] + src[5];
        dst[3] = src[2] + src[6];
        dst[4] = src[1] + src[5] + src[7];
        dst[5] = src[2] + src[4] + src[6] + src[8];
        dst[6] = src[3] + src[5] + src[9];
        dst[7] = src[4] + src[8];
        dst[8] = src[0] + src[5] + src[7] + src[9];
        dst[9] = src[6] + src[8];

        swap(src,dst);
    }

    int sum = 0;
    for( int i = 0; i < 10; ++i )
    {
        sum += src[i];
    }

    cout << "sum= " << sum << endl;
}

输出 sum= 14826
real time = 0.003s
user time = 0.002s
[解决办法]
这次的程序我竟然一次就写对了，不容易。效率高低容后再论，先贴上来

#include <iostream>
int G[10][5] =
{
{8, -1},
{2, 4, -1},
{1, 3, 5, -1},
{2, 6, -1},
{1, 5, 7, -1},
{2, 4, 6, 8, -1},
{3, 5, 9, -1},
{4, 8, -1},
{0, 5, 7, 9, -1},
{6, 8, -1}
};
#define NUM 8
//当某一位产生变化，其后的所有位都跟随变化
void Lv( int N[NUM], int i ) 
{
for (int m = i - 1 ; m >= 0 ; --m)
{
N[m] = G[N[m + 1]][0];
}
}
bool Next(int N[NUM])
{
int c = 1;
//NUM个数，只处理NUM－1个，最后一个数单独处理
for (int i = 0; i < NUM - 1; i++)
{
if(c == 0)
break;
else
{
//寻找本位上下一个数
int j = 0;
//先找当前数的位置
while(G[N[i + 1]][j] != N[i]) 
 
j++;
j += c;
if(G[N[i + 1]][j] == -1)
{//产生进位，后边的要依次捋直
//捋的动作发生在下一位上，当前位不用再管
c = 1;
}
else
{
c = 0;
N[i] = G[N[i + 1]][j];
Lv(N, i);
}
}
}
if(c == 0)
return true;
else
{
if(++N[NUM - 1] == 10)
{
return false;
}
else
{
Lv(N, NUM - 1);
return true;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int N[NUM];
//先产生第一个有效序列
N[NUM - 1] = 0;
Lv(N, NUM - 1);
int i = 0;
do 
{
i++;
for(int i = 7 ; i >= 0 ; i--)
{
std::cout<<N[i];
}
std::cout<<std::endl;
} while (Next(N));
std::cout<<"总共有"<<i<<"种情况\n";

system("pause");
return 0;
}

[解决办法]
可以看做这些号码是一系列数字的路径，那么直到叶节点的个数就是号码的总数。
我的思想是迭代。
如果最后一位数字是1，那么888*******1的出现次数 记为
#888*******1 = #888******21+#888*******41；
然后依次类推
#888******21 = #888*****121 + #888*****321 + #888*****521；
直到推到所有数字都填满。
如果出现#88813456221 即，最后一个我们推出的数字是1那么它的邻接点的个数是2.这就是迭代出口。加上即可。
总的算来时间复杂度是o（n） 空间是10 可以理解为o（m）, m为数字范围 因为存储了10个数字的邻接点 不管多少位数字的号码，都会从0-9里取出。所以跟号码长度没有关系，跟你取数字范围有关。至于你用什么数据结构，随意吧。数组，链表，神马神码。
这个算法的时间已经是线性时间了，如果有人可以用对数时间或者常数时间搞定一定M我一下。互相交流互相学习
[解决办法]
java版的，用的递归，一共14826个，发出来大家指教指教

public class Number
{
private static int sum = 0;
public static int[][] num = { { 0, 8 }, { 1, 2, 4 }, { 2, 1, 3, 5 }, { 3, 2, 6 },
{ 4, 1, 5, 7 }, { 5, 2, 4, 6, 8 }, { 6, 3, 5, 9 }, { 7, 4, 8 },
{ 8, 5, 7, 9, 0 }, { 9, 6, 8 } };

public static void main(String[] args)
{


int[] out= new int[8];
for (int i = 0; i < 10; i++)
{
out[0] = num[i][0];
for(int j = 1; j<num[i].length;j++)
{
out[1] = num[i][j];
getNext(out,out[1],1);
}

}

System.out.println("total:" + sum);
}

private static void getNext(int[] out, int nowNum,int position)
{
if (position == 7)
{
sum++;
for (int j = 0; j < 8; j++)
{
System.out.print(out[j]);
}
System.out.print("\n");
}
else
{
for (int i = 1; i < num[nowNum].length; i++)
{
out[position + 1] = num[nowNum][i];
getNext(out, out[position + 1], position + 1);
}
}

}
}
[解决办法]
介绍一个巧用整数类型实现四叉树搜索的方法。这个方法将树的路径表示为一个整数，树的搜索操作部分借用了ALU的硬件实现。

首先，第一位号码没有约束，共有10种情况，下面的算法重复10遍即可。

从第二位号码开始，每一位最多只有四种可能，用0~3来表示，对应的实际号码可查表求得。这样，除了第一位外，全部号码可以表示为一个四进制整数。（计算机中的整数是二进制的，这是一个很简单的转换）。这道题除第一位外一共7位号码，可以用14位二进制整数表示。第一位确定后，最多有2^14=16384种可能，所以只要扫描这16384种组合，然后滤掉不合规则的号码。

比如说四进制整数0-0000000，第一个号码0不用翻译。第二位0表示第一个号码0的第一个动作，查表得知0的第一个动作结果为8，所以第二个号码是8。第三位0表示第二个号码8的第一个动作，查表为0。依次类推，得到对应的电话号码为08080808。类似的，四进制数字9-1313131对应的电话号码为98989898。

在翻译每个四进制整数表示的号码时，从第二位逐次翻译到第八位。一旦发现某位不合规则，那么后面所有位的组合均为非法，可以直接跳过。跳过的方法是将前一位加一，并且从非法位开始，后面的所有位清成0。规则号码只需将最后一位加一，利用整数的进位操作自动调整前面各位的变化，相当于在一个指令周期内完成了各层的回溯与递进。

这个方法原理上仍然是树的深度优先搜索算法，只是没有使用常规的数据结构。优点是回溯与递进操作十分简单，没有递归。缺点是每次判断某一位是否合法时需要从树顶开始算，时间复杂度增加了一点。占用内存应当是各种算法中最小的，适合嵌入式系统。

#include <iostream>
using namespace std;

// 1 2 3
// 4 5 6
// 7 8 9
//   0

int matrix[][4] = {  8, -1, -1, -1,
                     2,  4, -1, -1,
                     1,  3,  5, -1,
                     2,  6, -1, -1,
                     1,  5,  7, -1,
                     2,  4,  6,  8,
                     3,  5,  9, -1,
                     4,  8, -1, -1,
                     0,  5,  7,  9,
                     6,  8, -1, -1
                  };

// 翻译并打印出四进制整数code对应的电话号码。
// 如果code含有非法动作，跳过第一个非法动作开始的所有号码

inline void translate_and_print_code( int first_digit, unsigned& code, unsigned& total )
{
    char text[] = "        ";
    text[0] = '0' + first_digit;
    int current_digit = first_digit;

    // 扫描第2位到第8位数字，每位是一个动作，将其翻译成相应的号码
    for( int digit_index = 1; digit_index <= 7; ++digit_index )
    {
        // 因为最多有四种动作，所以用两个二进制位表示一个号码位对应的动作
        int bit_index = ( 7 - digit_index ) * 2;
        unsigned action = ( code & ( 3 << bit_index ) ) >> bit_index;

        // 查表求得相应的号码
        current_digit = matrix[ current_digit ][ action ];

        // 遇到非法动作： 
 
        if( current_digit == -1 )
        {
            // 上一位前进一个动作，从本位以下的位清零
            bit_index += 2;
            code = ( ( code >> bit_index ) + 1 ) << bit_index;
            return;
        }

        // 合法动作：记录下来
        text[ digit_index ] = '0' + current_digit;
    }

    // 打印合法号码
    cout << text << endl;
    ++total;

    // 取得下一个四进制整数，各位数字联动进位
    ++code;
}

// 主函数，遍历所有第一位号码的情况

int main()
{
    unsigned total = 0;

    for( int first_digit = 0; first_digit < 10; ++first_digit )
    {
        unsigned code = 0;
        while( code < ( 1 << 14 ) )
        {
            translate_and_print_code( first_digit, code, total );
        }
    }

    cout << "total= " << total << endl;

    return 0;
}

查看更多 下一篇