2015騰訊線上筆試的一道程式設計題

摘要：昨天剛剛看了一道同學的騰訊線上筆試程式設計題;大緻如下：

要求求出未知數在1到100以内所有的可能組合,（橫着第三行的等式記不清楚了,自己随便添加的符号）

基本思路(1)以前沒有專門刷過題,第一次遇到這種題目,首先思考了一下常用的幾個算法,發現幾乎都不合适,因為這道題不是求解最優化的問題,也不容易劃分成問題不相幹的子集求解.唯一感覺有點可能的是回溯算法,因為涉及窮舉所有的可能.

(2)是以思考了一下暴力求解的可能,直接進行窮舉.發現這裡的計算與回溯思路基本相同,都是先做出一個決策(确定某個等式上的未知數值),然後遞歸的計算下一個等式的未知數.注意到前三個橫着的等式可以确定所有可能的未知數,而三個豎着的等式則是用來判斷這個些未知數到底符不符合所有的等式要求.

(3)思考到這裡基本架構就出來了,傳入一個變量Index用來确定到底是計算哪一個等式,同時判定是計算未知數還是驗證等式.當最後一個等式通過時就輸出所有未知數.

(4)然後需要思考的程式設計細節上的一些東西,這也是做題時最花時間的東西,

【1】首先要建構一個函數用來判斷是否滿足本次調用時應該滿足的等式,如果滿足就計算下一個,如果不滿足就要重新計算新的未知數.

【2】然後要注意每個等式和未知變量（定義為一個全局數組A【10】,A[0]不用）之間的關系,比如前三個等式的編号是1,2,3(index)，那麼每次确定的變量是A[3*index -2],A[3*index -1],A[3*index ].計算後三個等式時要将數組A【10】裡面的元素傳入驗證函數,這時候index(4,5,6)與A【10】的關系是傳入A[index - 3],A[index],A[index +3]

【3】做到這裡程式就可以運作了,但是還存在一些問題,首先第一個等式是比較特殊的,它的一個未知數是确定的9.但是由于函數遞歸調用要考慮所有等式的情況,是以還是得寫一個3重循環來進行周遊3個未知數.為了提高效率,我們可以在index == 1的時候進行一次跳轉,給未知數c直接指派,同時注意到等式變為a+b == 4+9 =13，那麼其實隻需要一重循環就可以了.這樣可以避免重複的計算.

【4】但是運作之後可以發現這樣的計算還是效率太低,計算機不足以在規定時間之内算出所有的解,提高效率是必須的.其實從等式1可以發現,含有三個未知數的等式隻需要兩重循環就可以得到所有符合該等式的解,但是難點就是每一個等式都不一樣,寫出一個通用的架構很麻煩.當然為了節約時間可以先進行一些顯而易見的提升.

【5】憑借國小數學知識就知道很多未知數是存在一個範圍的,比如第一個等式中的a+ b = 13,a，b不可能大于12,這樣就隻需要1到12的一次循環就可以了,同時第4個等式有a+c/f == 4,那麼a就不會超過3,這樣a的範圍就成了1到3.同理可以确定其他很多變量的範圍,而這些工作通過人為的分析可以提前完成,作為全局變量存儲.（要将所有變量的範圍計算精确可能不一定容易但是迅速的縮小到一個大概的範圍是不困難的）

如圖：

代表了範圍的最大值,最小值，沒有計算.比如第一個等式的a ≤ SA[1]。第index個等式的b ≤ SB[index]。

【6】通過這些修改程式可以很快的得出結果了,至于更麻煩的提高效率(循j減少環次數)更新在最後,畢竟這是一道筆試題，時間才是重要的.寫出這道程式大概花了2個多小時,因為第一次遇見這類題目,花了比較多的時間去思考和修改.但是如果再次碰見應該可以很快的做出來了,

#include "stdafx.h"
int A[] = {};
int SA[] = {,,,};
int SB[] = {,,,};
int SC[] = {,,,};
#define N 100
int Issatisfited(int a,int b,int c,int index)
{
    switch(index)
    {
              case  :
                  return   (a+b) == ;
              break;
                case  :
                     return   (a-b*c) == ;
              break;
                case  :
                     return   a+b*c == ;
              break;
                case  :
                     return   (a+b/c) == &&(b%c==);
              break;
                case  :
                return  (a - b*c) == ;
              break;
                case  :
                return  (a - b - c) == ;
              break;
    }
}
void Print()
{
    int i = ;
    while(i<=)
    {
        printf("%d ",A[i++]);
    }
    puts("\n");

}
void test(int index)
{
    int k,a,b,c;
    if (index <=)
    {
    for(a = ;a<=SA[index];a++)//計算所有可能的未知數.
    {
            if(index == )
                {
                    b =  - a;
                    c = ;
                    goto Test;
                }
        for(b = ;b<=SB[index];b++)
        {
            for(c = ;c<=SC[index];c++)
            {
                Test:if(Issatisfited(a,b,c,index))
                {
                    k = *index - ;
                    A[k] =  a;
                    A[k+] = b;
                    A[k+] = c;
                    test(index+);
                }
            }
        }
    }
}
    else//檢驗所有的結果
    {
        for(k = ;k<=;k++)
        {
            a = A[k] ;
            b = A[k+];
            c = A[k+] ;
                if(Issatisfited(a,b,c,k+))
                {
                    if(k == )
                        Print();
                }
                else
                    return;
        }
}
}

int _tmain(int argc, _TCHAR* argv[])
{
    test();
    return ;
}

           

=====================================

結果

更新::最多用到兩層循環.但是用了很多goto(這裡所有的goto都是向下進行的，減少出錯的可能,千萬不能往上走,很容易出錯),不是很好,而且使得程式的可讀性下降了很多.

void test(int index)
{
    int k,a,b,c;
    if (index <=)
    {
    for(a = ;a<=SA[index];a++)
    {
            if(index == )
                {
                    b =  - a;
                    c = ;
                    goto Test;
                }
        for(b = ;b<=SB[index];b++)
        {
                if (index == )//計算第二個等式
            {
                if(a>&&(a-)%b==)
                {
                    c = (a-)/b;
                    goto Test;
                }
                else
                    continue;
            }
                else if (index == )
                {
                    if(a>&&b%(a-)==)
                    {
                        c = b/(a-);
                        goto Test;
                    }
                    else 
                    continue;
                }
                Test:if(Issatisfited(a,b,c,index))
                {
                    k = *index - ;
                    A[k] =  a;
                    A[k+] = b;
                    A[k+] = c;
                    test(index+);
                }
        }
    }