[数据结构与算法]算法趣题-Q13

一、问题描述

?

二、问题分析

? ? ? ? 一种方法是直接暴力列举所有的排列数，再进行计算判定，那么需要进行10！次判断，效率太低，如代码实现中Python实现，但由于Python语言的友好，导致其代码数量少；

????????另一种方法是DFS深度优先遍历，并结合一些的剪枝操作，能够大量排除无效的排列，加快了运行速度，在我的C/C++实现中就是如此，当然也可以使用递归的方式避免重复编码（这里我将代码展开方便理清逻辑）。

三、代码实现

1.C/C++实现

#include <iostream>

using namespace std;

bool flags[10] = { false };

int carry = 0;
int myCount = 0;

// READ + WRITE + TALK = SKILL
// R, W, T, S 不为 0
// 从低位向高位DFS并进行剪枝
void DFS()
{
	for (int d = 0; d < 10; d++)
	{
		flags[d] = true;
		for (int e = 0; e < 10; e++)
		{
			if (flags[e])
				continue;
			flags[e] = true;
			for (int k = 0; k < 10; k++)
			{
				if (flags[k])
					continue;
				int sum0 = d + e + k;
				int carry0 = sum0 / 10;
				int l = sum0 % 10;
				if (flags[l])
					continue;
				flags[k] = flags[l] = true;
				for (int a = 0; a < 10; a++)
				{
					if (flags[a])
						continue;
					flags[a] = true;
					for (int t = 1; t < 10; t++)
					{
						if (flags[t])
							continue;
						int sum1 = a + t + l + carry0;
						int carry1 = sum1 / 10;
						if (sum1 % 10 != l)
							continue;
						flags[t] = true;
						for (int i = 0; i < 10; i++)
						{
							if (flags[i])
								continue;
							int sum2 = e + i + a + carry1;
							int carry2 = sum2 / 10;
							if (sum2 % 10 != i)
								continue;
							flags[i] = true;
							for (int r = 1; r < 10; r++)
							{
								if (flags[r])
									continue;
								int sum3 = r + r + t + carry2;
								int carry3 = sum3 / 10;
								if (sum3 % 10 != k)
									continue;
								flags[r] = true;
								if (flags[0])  // w, s 不能为0
								{
									int num[2];  // w, s
									int index = 0;
									for (int temp = 0; temp < 10 && index < 2; temp++)
										if (!flags[temp])
											num[index++] = temp;
									if (num[0] + carry3 == num[1] 
                                            || num[1] + carry3 == num[0])
										myCount++;
								}
								flags[r] = false;
							}
							flags[i] = false;
						}
						flags[t] = false;
					}
					flags[a] = false;
				}
				flags[k] = flags[l] = false;
			}
			flags[e] = false;
		}
		flags[d] = false;
	}
}

int main()
{
	DFS();
	cout << myCount << endl;
	return 0;
}

2.Python实现

# coding=utf-8

import itertools

if __name__ == '__main__':
    nums = '0123456789'
    count = 0
    chars = ['R', 'E', 'A', 'D', 'W', 'I', 'T', 'L', 'K', 'S']
    for item in itertools.permutations(nums):
        if item[0] == '0' or item[4] == '0' or item[6] == '0' or item[9] == '0':
            continue
        d = {chars[i]: item[i] for i in range(10)}
        if eval("{R}{E}{A}{D}+{W}{R}{I}{T}{E}+{T}{A}{L}{K}".format(**d)) == eval("{S}{K}{I}{L}{L}".format(**d)):
            count += 1
    print(count)