由24点引发的算法问题

[maiff]

由24点引发的算法问题

---

由来：

一个人大过年的跑去看乘风破浪，还可以但是最后镜头中出现一个算24的题目——7,7,6,1.算了半天我都没有算出来，但是我是不知道到底能不能算出来于是我就准备回去写一个能算任意四个数字的24的程序。于是我在回家的路上就构思什么样的逻辑。
肯定是穷举发把所有的可能性都例出来然后等于24的就是答案，无非就是4个数字4中运算符，因为是所有情况可以完全不用考虑括号，考虑括号其实也很简单就是一个中缀到后缀的转换。
回来说干就干，然后一上手就遇到一个问题，怎么列出4个数字的所有可能，隐约感觉出来要用递归，于是在没有搜索的情况下自己就开始干起来了。

全排列——自己想出来的解法

我的是一种递归思路，想知道4个数字的全排列，知道三个数字的全排列然后拿第四个数字去插空就好了，于是说干就干写出了下面的程序：

1. 首先需要一个函数去插空就是传入一个数组和一个数列出所有插空的可能。
2. 然后一个递归返回最后的可能，想明白了，程序写出来很简单但是因为后面我搜到更好的算法，于是把我这个方法删掉了，我有懒得写了这里就不再写了。

最后整个程序是写出来了，算了一下那个7761真的不能算24.来说一下我那个程序的思路，有更好的思路欢迎来讨论。

• 首先列出四个数字的所有可能
• 列出四个操作符的所有可能
• 因为最后一定是一个数字一个操作符然后我就把这两个当成两个队列一个一个按顺序shift
• 最后遇到一个难点，因为我用的是js，得到的字符串我直接用eval计算，但是我发现了一个问题，他自动会用科学计算来表示这可不是我想要的，于是专门写了一个calc的程序

function calc(arr,num_list){
	if(arr.length<=1) {
		num_list.push(arr[0])
		let str = num_list.join('')
		return eval(str)
	}
	else{
		let num = arr.shift()
		num_list.push(num)
		if(num_list.length===3){
			let str = num_list.join('')
			num_list=[eval(str)]
		}
		return calc(arr,num_list)
	}
}

然后最后得到了我想要的结果。

遐思：

但是我觉得我这个全排列的方法不好。不好在哪里呢？我用c语言不好实现，因为算法用js和用c实现那是不一样的用c显然更有成就感，于是我就上网去搜搜到一篇我看不懂的代码：

#include <stdio.h>  

int n = 0;  

void swap(int *a, int *b) 
{     
    int m;     
    m = *a;     
    *a = *b;     
    *b = m; 
}  
void perm(int list[], int k, int m) 
{     
    int i;     
    if(k > m)     
    {          
        for(i = 0; i <= m; i++)             
            printf("%d ", list[i]);         
        printf("\n");         
        n++;     
    }     
    else     
    {         
        for(i = k; i <= m; i++)         
        {             
            swap(&list[k], &list[i]);             
            perm(list, k + 1, m);             
            swap(&list[k], &list[i]);         
        }     
    } 
} 
int main() 
{     
    int list[] = {1, 2, 3, 4, 5};     
    perm(list, 0, 4);     
    printf("total:%d\n", n);     
    return 0; 
}  

看了半天没看懂，最后google半天终于看到一个好的解释文章是怎么说的我来解释一下。

我们知道全排列的含义就是一个序列所有的排序可能性，那么我们现在做这样的一个假设，假设给定的一些序列中第一位都不相同，那么就可以认定说这些序列一定不是同一个序列，这是一个很显然的问题。有了上面的这一条结论，我们就可以同理得到如果在第一位相同，可是第二位不同，那么在这些序列中也一定都不是同一个序列，这是由上一条结论可以获得的。
那么，这个问题可以这样来看。我们获得了在第一个位置上的所有情况之后，抽去序列T中的第一个位置，那guihua么对于剩下的序列可以看成是一个全新的序列T1，序列T1可以认为是与之前的序列毫无关联了。同样的，我们可以对这个T1进行与T相同的操作，直到T中只一个元素为止。这样我们就获得了所有的可能性。所以很显然，这是一个递归算法。
也就是第一个元素跟后面的元素全部交换的全排列。

详细看文章说的很详细。

总结

这篇文章就是总结一下我之前在百度面试回来的感觉就是，递归的应用真的很有用重点找到return和终止条件，然后就是要好好看看算法，下一个要好好看看动态规划。

[maiff]

def perm(list, start, end):
    if(start == end):
        print list
    for i in range(start,end):
        list[start],list[i] = list[i],list[start]
        perm(list,start+1,end)
        list[start],list[i] = list[i],list[start]

人生苦短，我用python