2022届高三信息技术选考总复习 专题20 约瑟夫问题 课件-（29张PPT）

(共29张PPT)
专题20 约瑟夫问题
1.任意一个数x Mod n值的范围是[__________]。
2.模型一：在一个0～n－1编号的位置中，从当前位置p向后移动k个位置，移动后的位置还是用0～n－1编号，可以用VB表达式_______________来表示移动后的位置。
3.模型二：在一个1～n编号的位置中，从当前位置p向后移动k个位置，移动后的位置还是用1～n编号，由于区间[1，n]可以用[0，n－1]＋____来表示，因此可以用VB表达式____________________来表示移动后的位置。
4.模型三：在环中循环向前移到位置k，即每次均要减去k，为保证被除数不为负数，需将被除数增加____，再进行Mod n运算。
0，n－1
(p＋k) Mod n
1
(p＋k－1) Mod n＋1
n
5.在一个0～n－1编号的位置中，从当前位置p向前移动k个位置，移动后的位置还是用0～n－1编号，可以用VB表达式________________来表示移动后的位置。
6.在一个1～n编号的位置中，从当前位置p向前移动k个位置，移动后的位置还是用1～n编号，由于区间[1，n]可以用[0，n－1]＋1来表示，因此可以用VB表达式______________________来表示移动后的位置。
(p－k＋n) Mod n
(p－k－1＋n) Mod n＋1
考点一　在区间[0，n－1]之间往后循环遍历各元素
由于任意数Mod n的范围是[0，n－1]，因此可以直接采用Mod运算。如一天可以分为24小时，分别用0点～23点表示。
p的初值 经历时长(k) 结果时间p VB表达式
p＝18时 3小时后 21 p＝(p＋k) Mod n
6小时后 0 38小时后 8 【例1】 对一段字符加密，加密规则为：①字母和数字都往后循环顺移3位，如“a”变为“d”，“y”变为“b”；“0”变为“3”，“7”变为“0”，②加密后字母在前，数字在后，③字母按逆序排列，数字按顺序排列，如输入明文“a1b7z8x3”，这密文为“aced4016”。 程序运行界面如图所示。实现上述功能的VB程序如下。
(1)根据加密规则，明文“9x7b”，则密文为__________。
(2)请在划线处填入合适的代码：
Private Sub Com_jm_Click()
Dim x As String，ch As String，c1 As String
Dim s1 As String，s2 As String，s As String
Dim i As Integer，n As Integer，p As Integer
x＝Text1.Text
n＝Len(x): s3＝”0123456789”： k＝3
For i＝1 To n
ch＝Mid(x，i，1)
If ch>＝”0” And ch <＝”9” Then
p＝Val(ch)
　　____①____
　　　　s1＝s1 & Mid(s3，p＋1，1)
ElseIf ch>＝”a” And ch <＝”z” Then
p＝Asc(ch)－Asc(”a”)
p＝(p＋k) Mod 26
　　____②____
End If
Next i
s＝s2＋s1
Text2.Text＝s
End Sub
答案　(1)ea20　(2)①p＝(p＋k) Mod 10　②s2＝Chr(p＋97) & s2 或s2＝Chr(Asc(”a”)＋p)＋s2
解析　(1)数字和字母分别构成环，关键要把“0”－“9”的字符转换成0－9的数字(用函数Val实现)，通过ASCII值实现a－z的字母转换成0－25的数字，再利用模型一可以得到答案。①中应该填写的代码是p位置向后移动k位置后的新位置。②应该填写的内容是把0－25的数字p加是97，使之成为小写字母的ASCII码值，转换成字母再反向连接。
【变式1】 某VB程序段如下：
s＝Text1.Text
For i＝1 To Len(s)
c＝Mid(s，i，1)
s1＝s1＋c
Next i
Text2.Text＝s1
程序运行时，在文本框Text1中输入“ABC123xyz”，在文本框Text2中输出“bcd123yza”，则加框处的代码为________。
A If c>＝”A” And c <＝ ”Z” Then c＝Chr(Asc(c)＋32)
If c>＝”a” And c <＝”z” Then
m＝(Asc(c)－Asc(”a”)＋1) Mod 26
c＝Chr(m＋Asc(”a”))
End If
B If c>＝”A” And c <＝”Z” Then
c＝Chr(Asc(c)＋32)
Else If c>＝”a” And c <＝”a”)＋1) Mod 26
c＝Chr(m＋Asc(”a”))
End If
C If c>＝”A” And c <＝”Z” Then c＝Chr(Asc(c)＋32)
If c>＝”a” And c <＝”z” Then
m＝(Asc(c)－Asc(”a”)) Mod 26＋1
c＝Chr(m＋Asc(”a”))
End If
D If c>＝”A” And c <＝”Z” Then
c＝Chr(Asc(c)＋32)
ElseIf c>＝”a” And c <＝”z” Then
m＝(Asc(c)－Asc(”a”)) Mod 26＋1
c＝Chr(m＋Asc(”a”))
End If
答案　A
解析　从运行结果来看，大写字母变小写字母，并且所有的小写字母往前移动1个位置。任何数Mod 26的值在[0，25]之间，因此先把字母转换成该区间的数字，再进行移位。把移位后的数字再变换成字母。而多分支结构只执行一条分支，大写字母仅仅转换成小写字母，没有移位。
考点二　在区间[1，n]之间往后循环遍历各元素
由于Mod n运算只能得到[0，n－1]之间的数，因此需要进行转换。
【例2】 编写VB程序，实现如下功能：在文本框Text1中输入当天对应的星期，文本框Text2中输入天数，单击“推算”按钮Command1，推算出相应天数后的星期情况，并在标签Label1中输出结果。界面如图所示。
(1)为实现上述功能，请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim x As String，xq As String，num As Integer
Dim i As Integer，h As Integer
x＝”日一二三四五六”
xq＝Text1.Text
i＝1
num＝Val(Text2.Text)
For i＝1 To Len(x)
If xq＝Mid(x，i，1) Then h＝i: Exit For
Next i
________
Label1.Caption＝”星期”＋Mid(x，r，1)
End Sub
(2)若当天是“星期五”，在文本框Text2中输入“169”，单击“推算”按钮后，标签Label1中显示的内容是________。
答案　(1)r＝(h＋num－1) Mod 7＋1 　(2)星期六
解析　星期在字符串中位置分别用1－7表示，因此符合模型二，先找出今天在星期中的位置6，(6＋169－1)Mod 7＋1＝7，在x字符中第7个位置是星期六。
【变式2】 若有40个同学排成一排，每位同学从1－40开始依次编号，让他们进行1、2、3依次报数，有如下VB程序段，加框处应修改为______________。
s1＝”一二三”： s＝””
For i＝1 To 40
s＝s＋Mid(s1，t，1)
If i Mod 3＝0 Then List1.AddItem s: s＝””
Next i
答案　t＝(i－1) Mod 3＋1
解析　学生进行1－3的报数，通过Mod 3运算，只能得到[0，2]之间的数，Mod 3之后需要＋1才能得1－3的结果，因此前面移动后需要减1。
考点三　往前循环遍历各元素
位置往往是一个正数，当往前移动时，可能得到一个负数，因此需将该数加上整数n，再进行相应的移位。
【例3】 某班师生玩一个游戏，n(n不超过1000)个同学站成一圈，逆时针编号为1～n，有两个老师A和B，A老师从1开始逆时针数k1个同学，B老师从n开始顺时针数k2个同学(注意A，B老师可能数到同一个学生)，被老师选中的1个或2个学生离开圈子，剩下的学生继续。程序开始时在Text1中输入同学数n，在Text2中输入k1的值，在Text3中输入k2的值，点击“开始”按钮，在Label1中显示依次出圈的学生编号。
想一想：数字1－7存储在stu数组中，分别对7名同学进行赋值，若该同学出圈，该同学所在位置的值为0。在第二轮数数中，AB教师是怎么开始数数的？
(1)程序运行如图所示，VB程序如下，划线处需要加上合适的代码。
Private Sub Command1_Click()
Dim stu(1 To 1000) As Integer，n As Integer，k1 As Integer，k2 As Integer
Dim pa As Integer，pb As Integer，left As Integer
n＝Val(Text1.Text): k1＝Val(Text2.Text): k2＝Val(Text3.Text)
For i＝1 To n
stu(i)＝i
Next i
left＝n：pa＝1: pb＝n
Do While left>0
s1＝k1: s2＝k2
If stu(pa) <>0 Then s1＝s1－1
Do While s1>0
　　____①____
If stu(pa) <>0 Then s1＝s1－1
Loop
If stu(pb) <>0 Then s2＝s2－1
Do While s2>0
If stu(pb) <>0 Then s2＝s2－1
Loop
Label1.Caption＝Label1.Caption & ” ” & pa
left＝left－1
If pa <>pb Then　Label1.Caption＝Label1.Caption & ” ” & pb: left＝left－1
stu(pa)＝0: stu(pb)＝0
Loop
End Sub
(2)虚线加框处的两条语句可以用一条语句来代替，该语句是______________。
答案　(1)①pa＝(pa＋1－1) Mod n＋1　②pb＝n　(2)pb＝(pb－1－1＋n) Mod n＋1
解析　可以通过For i＝1 To n或For i＝n To 1 Step －1循环，来实现从一个方向遍历数组或序列，是单方向的。在约瑟夫环中可以循环遍历各个元素的位置时，采用取余Mod n运算，该表达式值的范围在[0，n－1]中。若要在用[1，n]之间的位置来表示数据，需把该区间变换到[0，n－1]，再进行运算。在约瑟夫环中，可以向后移动，也可以向前移动位置，在向前移动位置时，需把被除数加上n，确保被整数成为正数，再进行取模运算。
【变式3】 (2020·9月A9协作体)有一字符串，由数字、字母和“－”组成，现以“－”为分组标记，作如下处理：数字往前移3位，如5→2，3→0，8→5，字母倒序放在各组前面；“－”不作处理。如字符串“25f－IT4－63t－”，经过处理后变为“f92－TI1－t30－”。下列VB程序段实现该算法：
Const mw＝”0123456789”
s＝Text1.Text: s1＝””： s2＝””
For i＝1 To Len(s)
c＝Mid(s，i，1)
If c>＝”0” And c <＝”9” Then
　　____(1)____
c＝Mid(mw，t＋1，1)
s1＝s1＋c
A
ElseIf c＝”－” Then
　　____(2)____
s1＝””
Else
　　____(3)____
End If
Next i
划线处的代码应该是(　　)
①s1＝c＋s1　②s2＝s2＋s1＋c　③s2＝c＋s2＋s1　④s1＝s1＋c　⑤t＝(7＋Val(c)) Mod 10　⑥t＝(Val(c)－3) Mod 10
A.⑤②① B.⑤③④ C.⑥①② D.⑥②①
解析　变量s1表示每段的字符，s2表示重新连接后的字符。数字往前移3位，将数字减去3后，可能出现负数，因此要先加10再Mod 10，也可以表达为该数字向后移7，因此(1)中内容为(Val(c)－3＋10) Mod 10。当取出字符是”－”时，表示一段已经结束，需将字符和”－”分别连接起来。Else分支表示当前是字母的情况。
1.将”0”－”9”的字符ch转换为数字的VB表达式________，反之将0－9的数字p转换为相应字符VB的表达式________。
答案　Val(ch)或Chr(t＋Asc(”0”))　Chr(t＋Asc(”a”))
2.将”a－z”字母转换为数字0－25的VB表达式________，反之将0－25的数字p表达为字符”a－z”字母的表达式________。
答案　Asc(ch)－97 或Asc(ch)－ Asc(”a”)　 Chr(p＋97) 或Chr(p＋ Asc(”a”))
3.将”a－z”字母转换为数字1－26的VB表达式________，反之将1－26的数字p表达为字符”a－z”字母的表达式________。
答案　Asc(ch) Mod 32　 Chr(p＋ Asc(”a”)－1)
4.若采用24点表示时间，当前时间p为18点，用VB表达式表示k个小时之前的钟点________。
答案　 (p－k＋24) Mod 24
5.若采用周一至周日表示星期，当前是星期一(p＝1)，用VB表达式表示k天之前的星期几________。
答案　(p－k－1＋7) Mod 7＋1
6.一个在[0，11]之间数p加密成一个新的数，加密规则为(p＋3) Mod 12，已知加密后的2个数分别为7和1，则这两个数加密前分别是________、________。
答案　4　8
解析　加密是把数循环向后移动3，解密的过程是把加密数据循环向前移动3位，即对加密后的数减去3。在环中循环向前移到位置k，即每次均要减去k，为保证被除数不为负数，需将被除数增加n，再进行Mod n运算。即(p－k＋n) Mod n。
7.有如下 VB 程序段：
Dim c As String，s1 As String
s＝Text1.Text: n＝Len(s)
s1＝””
For i＝1 To n
x＝Int(Rnd()*n)＋1
c＝Mid(s，x，1)
If x Mod 2＝0 Then
c＝Chr((Asc(c)－Asc(”a”)＋1) Mod 26＋Asc(”a”))
Else
c＝Chr((Asc(c)－Asc(”a”)＋25) Mod 26＋Asc(”a”))
End If
s1＝c＋s1
Next i
Text2.Text＝s1
在文本框Text1中输入“fight”，执行上述程序后，文本框Text2中输出不可能的是(　　)
A.ejfis B.jjffi C.sssss D.ieehs
解析　本题考查字符串和约瑟夫的应用。产生x的范围在[1，5]，变量c表示字符串s中任意一个字符，表达式Asc(c)－Asc(”a”)值的范围是[0，25]，该数加1后Mod 26是环的特征，表示该数向后循环增加1。因为环是一个首尾相连的数据结构，在n个元素的环中，向后移动t个位置与向前移动n－t效果是一样的，因此该数加25后Mod 26相当于向前移动一个位置。程序的功能是产生一个1－5的位置x，如果x是偶数，则向后移动一个位置，否则向前移到一个位置，并把他反向连接到s1中。A选项中依次产生的c为sifje，因此s是由t(x＝5)向前移动1个位置得来，j是i(x＝2)向后移动一位置得来，依次分析其他字符。
D
8.(2020·9月嘉兴基础测试)有如下VB程序段：
Const n＝10
Dim a(1 To 10) As Integer
m＝Int(Rnd*n＋1)
For i＝1 To n
a(i)＝0
Next i
i＝0: j＝0: c＝1: ans＝””
Do While c <＝3
i＝i Mod n＋1
If a(i)＝0 Then j＝j＋1
If j＝m Then
a(i)＝1: c＝c＋1
j＝0: ans＝ans＋Str(i)
End If
Loop
Text1.Text＝ans
执行上述程序段后，文本框Text1中不可能显示的内容是(　　)
A.2　4　6 B.7　4　2 C.5　10　6 D.6　2　8
D
解析　本题主要考查算法理解。m是[1，10]之间的一个随机数，a数组的初始值为0。可以理解为m个人围成一圈，数到第m个人时，当前指向的数对应的下标为1，可以理解为该值出列，且连接到ans，当三个值被连接后循环结束。i＝i Mod n＋1等效于i＝(i＋1－1) Mod n＋1，表示向前移一位，若i＝10，则前移的值为1。m是固定值，由四个选项的第一个数可知m为多少。如B项第一个值为7，m＝7，第二个值从8开始数，数到第7位时值为4，第三个值从5开始数，此时需注意第一次被连接的7对应的a数组值为1，需跳过，第三次被连接的值为2。D项m＝6，从下位7开始，数到第6位时值为2，再从3开始数为3、4、5、7、8、9，因a(6)已出列需跳过，第6位的值为9，故D项不可能。