Python算法100例-3.10 不重复的3位数

完整源代码项目地址，关注博主私信'源代码'后可获取

• 1.问题描述
• 2.问题分析
• 3.算法设计
• 4.确定程序框架
• 5.完整的程序
• 6.问题拓展

1．问题描述

用1、2、3、4共4个数字能组成多少个互不相同且无重复数字的三位数？都是多少？

2．问题分析

求互不相同的三位数，可以一位一位地去确定，先确定百位，再确定十位和个位，各位上的数值进行比较，若互不相同则输出。

3．算法设计

（1）利用多重循环嵌套的for语句实现。

（2）用三重循环分别控制百位、十位、个位上的数字，它们都可以是1、2、3、4。

（3）在已组成的排列数中，还要再去掉出现重复的1、2、3、4这些数字不满足条件的排列。

题目要求最后输出满足条件的数据个数，需要一个变量count充当计数器的作用，有一个满足条件的数据出现计数器的值加1。为了使每行能输出8个数字，每输出一个数字就对count的值进行判断，看是否能被8整除，若能整除则输出换行符。

if count % 8 == 0:
    print()

4．确定程序框架

该程序的流程图如图所示。

5．完整的程序

完整的程序如下：

%%time
# 不重复的3位数

if __name__ == "__main__":
    count = 0                                       # 计数器
    for i in range(1, 5):
        for j in range(1, 5):
            for k in range(1, 5):
                if i != k and i != j and j != k:    # 判断三个数是否互不相同
                    count += 1
                    print("%d%d%d  " %(i,j,k), end=" ")
                    if count % 8 == 0:
                        print()
    print("三位互不相同的数，共有：%d" %count, "个")

123   124   132   134   142   143   213   214   
231   234   241   243   312   314   321   324   
341   342   412   413   421   423   431   432   
三位互不相同的数，共有：24 个
CPU times: user 500 µs, sys: 0 ns, total: 500 µs
Wall time: 487 µs

6．问题拓展

上面的程序段的效率比较低，因为无论i与j的值是否相等，k都要从1到4把所有的值遍历完。根据题目要求，只要i与j的值相等，那么k的取值就没必要进行，因为无论k的值是多少，最后组成的三位数中总有相同的数字。对于本题来说，因取值范围较小，算法效率的高低相差并不大，但是对于取值范围大的题目，两种算法的效率相差是很明显的。程序代码可改写如下：

%%time
#  不重复的3位数

if __name__=="__main__":
    count = 0                                                               # 计数器
    for i in range(1, 5):
        for j in range(1, 5):
            k = 1
            while k < 5 and j != i:
                if k != j and k != i:
                    print("%d%d%d  " %(i,j,k), end=" ")
                    count += 1
                    if count % 8 == 0:              # 每输出8个换一行
                        print()
                k += 1
    print("三位互不相同的数，共有：%d" % count, "个")

123   124   132   134   142   143   213   214   
231   234   241   243   312   314   321   324   
341   342   412   413   421   423   431   432   
三位互不相同的数，共有：24 个
CPU times: user 1.09 ms, sys: 106 µs, total: 1.19 ms
Wall time: 1.11 ms