每周一练：直接选择排序

vlambda
2022-02-09

每周一练：直接选择排序

每周一练

上期我们给出的题目是：求10000以内的水仙花数？

首先普及一下水仙花数的概念：水仙花数（Narcissistic number）也被称为超完全数字不变数（pluperfect digital invariant, PPDI）,是指一个 n 位数（n≥3 ），它的每个位上的数字的 n 次幂之和等于它本身（例如：1^3 + 5^3+ 3^3 = 153）。

陈剑同学给出的参考答案：

#第一次提交的答案

numbers1=[]
numbers2=[]
for number in range(100,1000):
    if len(str(number)) ==3 and number==int(str(number)[0])**3+int(str(number)[1])**3+int(str(number)[2])**3:
        numbers1.append(number)
for number in range(1000,10000):
    if len(str(number)) ==4 and number==int(str(number)[0])**3+int(str(number)[1])**3+int(str(number)[2])**3+int(str(number)[3])**3:
        numbers2.append(number)
print(numbers1)
print(numbers2)

#第二次提交的答案

for i in range(100,10000):
    a=i//100
    b=i//10%10
    c=i%100
    if i==a**3+b**3+c**3:
        print(i)

Edmond Dou同学给出的修改建议：

陈剑的第一组程序比较简洁，但是c的赋值不准确，可改为c=i-a*100-b*10，结果是153,370,371,407。

只在此山中同学给出的参考答案：

def panduan(n):
    ns = str(n)
    count=len(ns)
    sum=0
    for i in ns:
        sum+=int(i)**count
    if sum==n:
        print "this is np number:",n
for num in range(100,10000):
     panduan(num)

我们给出的简化参考答案是这样的：

print [x for x in range(100,10000) if sum(i**len(str(x)) for i in [int(j) for j in str(x)])==x]

其实本质上就是将数字转换成字符串，然后取出字符串的中每个字符再次转换成数字进行求幂计算。

今天我们给出的题目是：直接选择排序

直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

欢迎大家在文章下留言，提交自己的解答。

每周一练：直接选择排序