算法学习(十三),算法学习

1.Funny Words Generator

  说明:编写一个程序,可以生成一组有趣的单词。

  让我们按照以下步骤进行工作:

  1.单词有任意数量的字母,但是字母在奇数位置(1、3、5、……)应该是辅音,而字母的偶数位置(2、4、6、……)应该是元音。

  2.规定辅音字母是 bcdfghjklmnprstvwxz,元音是 aeiou (注意q和y跳过)。

  3.用参数实现简单的线性同余生成器,参数A=445,C=700001,M=2097152,初始值X0作为输入数据(即种子)。公式:Xnext = (A * Xcur + C) % M

  4.要生成由N个字母组成的单词,用这个生成器生成的随机数作为初始值,生成下一个随机数,例如,在X0=0和N=4的情况下,你将得到
700001,1821950,1967079,1537772 这四个数。

  5.将这些随机值转换为字母,通过对辅音或5元音的位置进行索引,并从上面的字符串中选择字母(参见步骤2)。

  例如,如果X0=0我们要生成4个字母的单词,我们有如下的计算:

Random Value       Letter Index        Letter
   700001         700001 % 19 = 3        F   # f的索引为3,那么就在辅音的第四个位置上。
  1821950        1821950 % 5  = 0        A   # a的索引为0,那么就在元音的第一个位置上。
  1967079        1967079 % 19 = 9        M
  1537772        1537772 % 5  = 2        I

  因此得到的单词是fami。

  输入数据:在第一行中包含生成的单词数量和随机生成器的种子值X0。
  下一行中包含应该生成的单词长度,并与空格分隔。
  答案:应该包含你所生成的单词,并由空格分隔。

  例如:

input data:
3 0
4 5 6

answer:
fami wovaw kelasi

  另一个例子:

input data:
4 2014
9 9 9 9

answer:
foravanad zibecefeb wagabenip wedivonow

  测试数据:

23 344985
4 3 6 7 6 8 3 8 7 7 4 6 6 8 7 7 8 3 6 8 3 8 6

  代码如下:

 1 consonant = 'bcdfghjklmnprstvwxz'
 2 vowels = 'aeiou'
 3 
 4 test_case = input().split()  # 测试用例数
 5 
 6 A = 445
 7 C = 700001
 8 M = 2097152
 9 X = int(test_case[1])
10 nums = [int(i) for i in input().split()]
11 for N in nums:
12     total = []    # 找到生成的随机数
13     while N > 0:
14         N -= 1
15         X = (A * X + C) % M  
16         total.append(X)
17     letters = []
18     for i in total:
19         if total.index(i) % 2 == 0:
20             n = i % 19
21             letter = consonant[n]   # 通过索引找到字符
22             letters.append(letter)
23         elif total.index(i) % 2 != 0:
24             n = i % 5
25             letter = vowels[n]
26             letters.append(letter)
27         word = ''.join(letters)  # 合并字符
28     print(word, end=' ')
29 
30 输出:hodu tob vapola cizilah selapi hirugife wam nocofavo buhinut xuweduf suto gonobe rinuki votawezu juragah topilin rawotisi nij facicu gucocada jen lebumuci fuline

 

算法学习(十三),算法学习

2.Tic-Tac-Toe

  说明:井字游戏的一种算法——检查功能,它可以判断游戏是否结束,并由一个或另一方获胜。

  这个游戏是在方块3 x 3上进行的。让我们假设这些方块命名为1到9个数:

 1 | 2 | 3
---+---+---
 4 | 5 | 6
---+---+---
 7 | 8 | 9

  两名玩家将他们的标记(X为第一,O为第二)依次转换为任何剩余的数字方块。一方完成了3个标记(3个x或3个o)的直线,马上就会赢。即每行每列和两个对角线,共8中赢的情况。例如,下面是X和O的步骤:

 X   O
-------
 7
     5
 4
     1
 9
     2
 8

  上面步骤形成了下面的方块情况:

 O | O |  
---+---+---
 X | O |  
---+---+---
 X | X | X

  第一个玩家(X字)通过第三排连成一线,赢的游戏。

  问题陈述:

  你将得到一系列的移动序列(假设第一步是由X完成的),由标记被放置的单元格的数量,而你的任务是确定哪一步完成了连成一线的情况(任何一方连成一线都可以,不过要最先完成的一方)。

  输入数据:第一行中包含测试用例数。

  下面每行有一个测试用例——正好是9个数字,描述了按顺序执行的单元格。

  答案:应该包含玩家在游戏中获胜时在第几步(从1开始计,到9为止,共9步,即输出在第几步获胜),如果在最后一次移动后(没有赢家)没有玩家获胜则输出
0 。

  例如:

input data:
3
7 5 4 1 9 2 8 3 6   # 在第7步获胜
5 1 3 7 6 4 2 9 8   # 在第6步获胜
5 1 2 8 6 4 7 3 9   # 没有人获胜,输出0

answer:
7 6 0

  测试数据:

15
9 7 6 8 5 3 2 1 4
4 1 5 6 3 8 2 9 7
1 8 2 5 4 3 7 9 6
4 8 5 1 9 6 2 3 7
7 6 9 4 5 2 1 8 3
8 4 9 5 3 7 1 2 6
9 3 8 7 6 1 5 2 4
8 3 9 2 1 4 6 7 5
1 7 8 9 6 2 5 4 3
6 1 5 2 4 3 7 9 8
8 9 1 6 7 4 2 3 5
3 9 1 7 2 5 4 8 6
9 5 1 4 8 3 6 7 2
1 5 4 8 9 3 6 2 7
6 8 9 3 2 1 4 5 7

  代码如下:

 1 test_cases = int(input())
 2 win = [
 3     {1, 2, 3},
 4     {4, 5, 6},
 5     {7, 8, 9},
 6     {1, 4, 7},
 7     {2, 5, 8},
 8     {3, 6, 9},
 9     {1, 5, 9},
10     {3, 5, 7}
11 ]
12 # 所有赢的比赛的位置条件
13 
14 def ans(Xs, Os):
15     A = []
16     for i in win:
17         if i & Xs == i or i & Os == i:  # 如果win中的子集和Xs或Os的交集等于子集自己,表示有人赢的游戏
18             a = max(data.index(x) for x in i) + 1  # 找到一方赢的游戏是的索引位置
19             A.append(a)
20     if len(A) > 0:
21         print(min(A), end=' ')  # 最先赢的游戏的索引
22     else:
23         print(0, end=' ')   # 都没有赢
24 
25 for _ in range(test_cases):
26     data = [int(m) for m in input().split()]
27     Xs = set(data[::2])  # X的位置
28     Os = set(data[1::2]) # O的位置
29     ans(Xs, Os)
30 
31 输出:9 9 7 0 7 9 8 9 0 5 8 5 8 8 0

 

1.Funny Words
Generator 说明:编写一个程序,可以生成一组有趣的单词。
让我们按照以下步骤进行工作: 1.单词…

发表评论

电子邮件地址不会被公开。 必填项已用*标注