本次的题目如下所示(原题出处:蓝桥杯):
【提示信息】
一个正整数如果任何一个数位小于等于右边相邻的数位,则称为一个数位递增数。
例如:
1135是一个数位递增数
1024不是一个数位递增数
【编程实现】
输入一个正整数 n(10<n<10001),输出10到n (包含10和n)中有多少个数位递增数。
输入描述:输入一个正整数 n(10<n<10001)
输出描述:输出10到n中有多少个数位递增数
【样例输入】
15
【样例输出】
5
【上述输入输出样例的进一步解释】
用户输入的正整数,即样例输入为15,10到15之间的数位递增数有:11、12、13、14、15。所以样例输出为5。
这一题是典型的枚举题型,这种题型我们需要解决两个问题:
- 枚举的范围
- 判断的条件
从题目中我们可以看出,枚举的范围从10开始到输入的数为止。我们很明显可以得到范围是range(10, n+1),根据递增数的定义,10明显可以被排除掉,因此枚举的范围可以定义为range(11, n)。
剩下要解决的关键问题是判断的条件。在第2讲中,我们已经讲过如何得到一个整数各个数位上的数值了。我们将各个数位上的数存到一个列表中,并对相邻的两项进行大小比较。满足条件即可确定该数为递增数。
由于判断相邻两项大小比较需要在循环中进行,我们在解决此类问题时有一个比较通用的做法。在循环之前我们定义一个布尔型的变量为True或False,循环的过程中遇到不满足条件(满足条件)的情况时直接将布尔型的变量变成False(True)并退出循环。
由此我们可以得到本道题的伪代码如下:
n = 输入的整数
m = 0 # 计数用
for i in range(11, n+1):
l = 列表(i的各个数位上的数)
flag = True
for j in range(len(l)-1):
if l[j] > l[j+1]:
flag = False
break
if flag == True:
m += 1
print(m)
通过伪代码,我们可以得到Python的代码如下:
n = int(input())
m = 0
for i in range(11, n + 1):
l = []
t = i
while t > 0:
l.append(t % 10)
t //= 10
l.reverse()
flag = True # 默认为递增数
for j in range(len(l)-1):
if l[j] > l[j+1]:
flag = False # 不满足条件,不是递增数
break
if flag:
m += 1
print(m)
该题目是一条综合题,考查范围包括枚举算法、十进制数的本质、列表相邻值大小比较等,题目难度:★★★★
这类题型由多个知识点组成,每个知识点本身并不是太难,难度在于综合应用。此类考查综合应用能力的题目可以出很多,一般都是枚举类型的题型,判断条件需要进行多次计算才能得到。
我们可以看一道经典的题目:
一个数除了1和它本身之外,不能被其他任何数整除,这个数被称为素数(或质数)。编写一个程序,计算出100以内所有的素数并打印。
输入:
无
输出:
所有的素数,并以空格隔开
这道题我们可以很明显看出来,是一道枚举题。枚举的范围是1到100,由素数的定义,我们可以得出1不是素数,枚举的范围从2到100。
关键的问题是如何判断。那我们将这个数从2开始除,一直除到比这个数小1的数,如果都不能被整除说明这个数就是素数。代码我们可以写成这样:
prime = []
for i in range(2, 100):
flag = True
for j in range(2, i):
if i % j == 0:
flag = False
break
if flag:
prime.append(i)
print(*prime)
当然,这个代码还需要进一步优化,我们有必要一直除到比这个数小1的数吗?答案是肯定没必要。一个合数将它分解成两个数的乘积,是由一个小一些的数乘一个大一些的数,最中间的情况是两个相同的数相乘。如果到达这个数的平方根,还没有因子,已经说明它是素数,后面更大的数根本没必要判断了。因此我们可以缩小内层循环的范围:
from math import sqrt, ceil
prime = []
for i in range(2, 100):
flag = True
for j in range(2, ceil(sqrt(i))):
if i % j == 0:
flag = False
break
if flag:
prime.append(i)
print(*prime)