【趣味算法】定义四位整数 abcd，从 0000 到 9999 范围内，输出所有符合如下规则的四位整数

整数 abcd，从 0000 到 9999 范围内，输出所有符合如下规则的四位整数"/>

【趣味算法】定义四位整数 abcd，从 0000 到 9999 范围内，输出所有符合如下规则的四位整数

文章目录

• 一、题目描述
• 二、题目分析
• 三、代码实现

朋友去面试，面试官问到的一个问题。

一、题目描述

定义四位整数 abcd，从 0000 到 9999 范围内，输出所有符合如下规则的四位整数：

1. a < b < c < d
2. a + b + c + d == 20

示例：

正确：0389、1289
反例：2398、6789

二、题目分析

• 方法1：暴力破解，定义四层循环，符合条件即输出；方法简单，时间复杂度高：O(n^4)
• 方法2：优化方法1，归纳出 a、b、c、d 的实际取值范围，减少循环次数；根据条件，a 取值可以总结为：a + (a+1) + (a+2) + (a+3) <= 20；得出：0<=a<=3.5；
  同理：b 的取值：a+1<=b<=(20-3-a)/3；c 的取值：b+1<=c<=(20-1-a-b)/2；d 直接计算可得。
• 方法3：递归求解，面试官提出的实现方式，暂时未想到如何实现。

三、代码实现

/*
计算所有满足要求的四位数字序列[abcd]，要求如下：
1. a<b<c<d
2. a+b+c+d==20
*/
package main
import "fmt"func main() {fmt.Println("-----------------[循环]------------------")f0()fmt.Println("-----------------[优化循环]------------------")f1()fmt.Println("-----------------[递归]------------------")f2()
}// 暴力破解
func f0() {for a := 0; a <= 9; a++ {for b := 0; b <= 9; b++ {for c := 0; c <= 9; c++ {for d := 0; d <= 9; d++ {if a+b+c+d == 20 && a < b && b < c && c < d {fmt.Printf("%04d\n", a*1000+b*100+c*10+d)}}}}}
}// 优化取值范围
func f1() {for a := 0; a <= (20-6)/4; a++ {for b := a + 1; b <= (20-3-a)/3; b++ {for c := b + 1; c <= (20-1-a-b)/2; c++ {d := 20 - a - b - cif d <= 9 {fmt.Printf("%04d\n", a*1000+b*100+c*10+d)}}}}
}
// 递归实现打印输出
func f2() {// TODO
}

运行结果：

-----------------[循环]------------------
0389
0479
0569
0578
1289
1379
1469
1478
1568
2369
2378
2459
2468
2567
3458
3467
-----------------[优化循环]------------------
0389
0479
0569
0578
1289
1379
1469
1478
1568
2369
2378
2459
2468
2567
3458
3467
-----------------[递归]------------------

——2019-07-26——