首页 > 代码库 > 0~9十个数，每个数只能使用一次，组成两个三位数相加和为四位数的算法
0~9十个数，每个数只能使用一次，组成两个三位数相加和为四位数的算法
这几天上网，看到百度里面有人问这一道题目,0~9十个数，组成如下加法式 *** + *** = ****，每个数字都只能使用一次，问一共多少中组合？
今天，就用C#语言来写一下，解出这道题，其他语言算法相同，只是语法不同，这里由于时间关系，不再贴出代码。
这里先讲解一下思路，首先我们是程序员，不是数学家，我们是站在编程的角度思考问题。这里是两个三位数相加，得到一个四位数，所有数字不能重复，那么最小的三位数是123，最大的三位数是987，确定循环的范围，当然你非要用100到999也可以，不过就是效率低一些罢了。
通过循环，得到两个三位数后，然后就是将两个数相加，得到他们的和，验证和是否为四位数、是否重复使用了数字。当然这两个可以放到一起验证，我的思路是，将两个三位数和他们的和，拼成一个字符串，然后判断0~9哪个数字不存在字符串中，只要有一个不存在，就不符合条件，只有0~9都存在，才是正确结果。
下面用代码来实现一下，打开VS2010，新建一个控制台程序，打开Program.cs开始编写代码，全部代码如下：
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace TestConsoleApp{ class Program { static void Main(string[] args) { long start = DateTime.Now.Ticks; //实例化PrintNum类 PrintNum pNum = new PrintNum(); pNum.printNumbers(); long useTime = DateTime.Now.Ticks - start; Console.WriteLine("Time used:" + useTime / 10000 + "ms"); Console.Read(); } } public class PrintNum { public void printNumbers() { int result = 0; int lineNum = 1; for (int i = 123; i <= 987; i++) { for (int j = 123; j <= 987; j++) { result = i + j; if (isTrue(result, i, j)) { Console.Write(lineNum.ToString("00") + ": "); Console.Write(i + " + "); Console.Write(j + " = "); Console.Write(result + "\t"); //每行显示三个 if (lineNum % 3 == 0) { Console.WriteLine(); } lineNum++; } } } } public bool isTrue(int result,int i,int j) { String str = "0123456789"; String s = result + "" + i + "" + j; for(int k = 0;k < str.Length;k++) { if (!s.Contains(str[k])) { return false; } } return true; } }}
这里写了一个PrintNum类，将方法封装到类里面，然后在main方法中实例化该类，调用方法输出结果。结果如下：
这是常规写法，代码没有经过优化，看到执行这个过程一共消耗了474ms.下面是经过优化的代码：
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace TestConsoleApp{ class Program { static void Main(string[] args) { long start = DateTime.Now.Ticks; //实例化PrintNum类 PrintNum pNum = new PrintNum(); pNum.printNumbers(); long useTime = DateTime.Now.Ticks - start; Console.WriteLine("Time used:" + useTime / 10000 + "ms"); Console.Read(); } } public class PrintNum { public void printNumbers() { int result = 0; int lineNum = 1; for (int i = 123; i <= 987; i++) { for (int j = 987; j >= 123; j--) { result = i + j;
if (result > 1000) { if (isTrue(result, i, j)) { Console.Write(lineNum.ToString("00") + ": "); Console.Write(i + " + "); Console.Write(j + " = "); Console.Write(result + "\t"); //每行显示三个 if (lineNum % 3 == 0) { Console.WriteLine(); } lineNum++; } } else { break; } } } } public bool isTrue(int result,int i,int j) { String str = "0123456789"; String s = result + "" + i + "" + j; for(int k = 0;k < str.Length;k++) { if (!s.Contains(str[k])) { return false; } } return true; } }}
执行结果如图：
执行共耗时315ms,一下减少了100多毫秒，当然我的电脑性能好，在性能差一点的电脑上面，差别就不是这么多了。优化的思路是，内循环从大到小，当两个数相加小于1000及不是四位数时，退出本次循环。就是减少了循环次数。
是的，你没看错，前面的是序号，一共96个结果。说实话，我也没想到会有这么多。。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。