24點計算 --- 龐果

問題描述

24點遊戲是一種使用撲克牌來進行的益智類遊戲，遊戲内容是:

• 從一副撲克牌中抽去大小王剩下52張，任意抽取4張牌
• 把牌面上的數（A代表1）運用加、減、乘、除和括号進行運算得出24。
• 每張牌都必須使用一次，但不能重複使用。

有些組合有不同種算法，例如要用2，4，6，12四張牌組合成24點，可以有如下幾種組合方法：

• 2 + 4 + 6 + 12 = 24
• 4 × 6 ÷ 2 + 12 = 24
• 12 ÷ 4 × (6 + 2) = 24

當然，也有些組合算不出24，如1、1、1、1 和 6、7、8、8等組合。”

請完成函數can24，4張牌如果可以組成24點，傳回1，不能則傳回0。

友情提醒

注意以下這些組合：

• 1 1 1 10 不可以
• 6 6 6 6 可以
• 5 5 5 1 可以，即可以用分數，如(5-1/5)*5 = 24
• 1 1 1 11 可以

算法說明

使用的比較傻的遞歸算法

• 首先找出4個數的全排，然後一個一個全排去嘗試
• 嘗試的時候，從4個數中任意選兩個組合四則運算，得出的結果和剩下的元素組成新數組，然後又任意選兩個運算，直到數組為1看結果，輸出。

算法很簡單，玩一玩了。。。我感覺可以用動态規劃來優化一下，懶得搞了。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>    
#include <cmath> 
#include <vector>
using namespace std;

#define SWAP(t, a, b) do {t v=a; a=b; b=v;} while (0)

#define OP(o,t,a,b) { t = a o b;}


int _can24(vector<double> &numbers)
{
    vector<double> tmp=numbers;
    //cout << tmp.size() << endl;
    if(numbers.size()==1)
    {
        if((numbers[0]-24<1e-8) && (numbers[0]-24>-1e-8))
        {
            //cout << " Res :" << numbers[0] << endl;
            return 1;
        }
        else
        {
            //cout << " Res :" << numbers[0] << endl;
            return 0;
        }
            
    }
    
    for(int i=0;i<numbers.size();i++)
    {
        for(int j=i+1;j<numbers.size();j++)
        {
            if(i!=j)
            {
                //cout << " A: " << numbers[i] << " B: " << numbers[j] << endl;
                //tmp[i]=numbers[i]+numbers[j];
                tmp.erase(tmp.begin()+j);
                OP(+,tmp[i],numbers[i],numbers[j]);
                if(_can24(tmp)==1)
                    return 1;
                
                OP(-,tmp[i],numbers[i],numbers[j]);
                if(_can24(tmp)==1)
                    return 1;
                
                OP(*,tmp[i],numbers[i],numbers[j]);
                if(_can24(tmp)==1)
                    return 1;
                
                
                if(numbers[j]>1e-8 || numbers[j]<-1e-8)
                {
                    OP(/,tmp[i],numbers[i],numbers[j]);
                    if(_can24(tmp)==1)
                        return 1;
                }
                
                
                tmp=numbers;
            }
            
            
        }
    }
    
    return 0;
    
}


int can24(int a, int b, int c, int d)
{
    vector<double> numbers;
    
    numbers.push_back((double)a);
    numbers.push_back((double)b);
    numbers.push_back((double)c);
    numbers.push_back((double)d);
    //numbers.push_back((double)d);
    
    //__can24(numbers);
    vector<double> tmp=numbers;
    
    for(int i=0;i<numbers.size();i++)
    {
        SWAP(double,numbers[0],numbers[i]);
        for (int j = 1; j < numbers.size(); ++j ) {
            SWAP(double,numbers[1],numbers[j]);
            for(int p=2;p<numbers.size();p++)
            {
                SWAP(double,numbers[2],numbers[p]);
                
                tmp=numbers;
                
                if(_can24(numbers)==1)
                    return 1;
                

                numbers=tmp;
                                
                SWAP(double,numbers[2],numbers[p]);
            }
            SWAP(double,numbers[1],numbers[j]);
        }
        SWAP(double,numbers[0],numbers[i]);
    }
    
    
    return 0; 
}



//start 提示：自動閱卷起始唯一辨別，請勿删除或增加。
//可不完成，完成功能函數即可，給定主函數，是為友善你測試
int main(){
        //
    cout << can24(8,7,8,8) << endl;
    cout<<can24(6,6,6,6)<<endl;  
    cout<<can24(1,1,1,10)<<endl;  //不可以   
    cout<<can24(5,5,5,1)<<endl;  
    cout<<can24(1,1,1,11)<<endl; 
    return 0;
}