2020-11-08 Windows应用程序设计作业（Python版实现）（一）简单语法-python黑洞网

'''
函数名称：test_for_rule
函数功能：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，
         得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。
最新版本：2020/10/20
'''
def test_for_rule(n, change_list):
    change_list.append(n)
    if n == 1:                      # 若干次后结果为1 （递归出口）
        return
    if n % 2 == 1:                  # 该自然数为奇数
        n = (int) (n * 3 + 1)
    else:                           # 该自然数为偶数
        n = (int) (n / 2)
    test_for_rule(n, change_list)   # 递归调用

'''
主 函 数（程序入口）
最新版本：2020/10/20
作    者: ZhaoYiman
'''
if __name__ == '__main__':
    while True:
        n = (int)(input("Please input a nature number:"))   # 输入一个自然数
        change_list = []                                    # 创建一个list列表，存所有的变化过程
        test_for_rule(n,change_list)                        # 函数调用
        print(change_list)                                  # 结果输出

2、给定一个含有n个元素的数组，找出数组中的两个元素X和Y使得abs（x-y）最小。

'''
函数名称：find_two_elements
函数功能：给定一个含有n个元素的数组，找出数组中的两个元素X和Y使得abs（x-y）最小。
最新版本：2020/10/20
'''
def find_two_elements(n_array):
    n_array.sort()     # 原数组排序
    diff_array = []    # 依次存储相邻两值之差
    for i in range(len(n_array) - 1):
        diff_array.append(abs(n_array[i+1] - n_array[i]))
    # print(diff_array)
    value, x, y = 0, n_array[0], n_array[1]   # 初始化
    for i in range(len(diff_array)):          # 遍历整个差值数组，并进行动态修改
        if diff_array[i] < diff_array[value]:
            value, x, y = i, n_array[i], n_array[i+1]
    return x, y                               # 返回结果，两个差值最小的元素

'''
主 函 数（程序入口）
最新版本：2020/10/20
作    者: ZhaoYiman
注    释：Python 没有内置对数组的的支持，但可以使用 Python 列表代替。
'''
if __name__ == '__main__':
    n = (int)(input("Please input the number of the array:"))
    tmp = input("Please input n elements:")
    array = [int(i) for i in tmp.split()]         # 以空格为分割，存储n个元素
    x, y = find_two_elements(array)
    print(f'数组中使得abs(x-y)最小的两个元素为：{x}, {y}')

3、生成学号后四位开始的100之内的30个随机数用两种算法进行排序（其中一个为递归算法）。

import random
'''
函数名称：random_array
函数功能：生成学号后四位开始的100之内的30个随机数
最新版本：2020/10/21
'''
def random_array(beg):
    end = beg + 100
    r_array = random.choices(range(beg, end + 1), k = 30, weights = range(beg, end + 1))   # 方法一：随机生成30个，可能重复
    # r_array = random.sample(range(beg, end + 1), 30)                                     # 方法二：随机生成30个，不会重复  
    return r_array                                     

'''
函数名称：partition
函数功能：快速排序的一次划分函数
最新版本：2020/10/21
# r_array[]: 排序数组
# low      : 起始索引
# high     : 结束索引
'''
def partition(r_array:list, low:int, high:int):
    i, j, tmp = low + 1, high, r_array[low]
    while True:
        while i < high and r_array[i] <= tmp :           # 使用i+=1必须要及时使用哨兵，跳过重复的元素，防止重复元素之间交换形成死循环
            i += 1
        while j > low and r_array[j] >= tmp:             # 原理同上
            j -= 1
        if i >= j:
            break
        r_array[i], r_array[j] = r_array[j], r_array[i]   # 交换

    r_array[low], r_array[j] = r_array[j], r_array[low]
    return j

'''
函数名称：QuickSort
函数功能：快速排序 —— 递归算法
最新版本：2020/10/21
# r_array[]: 排序数组
# low      : 起始索引
# high     : 结束索引
'''
def QuickSort(r_array, low, high): 
    if low >= high:
        return
    piviot = partition(r_array, low, high)
    QuickSort(r_array, low, piviot - 1)
    QuickSort(r_array, piviot + 1, high)

'''
函数名称：QuickSortNonR
函数功能：快速排序 —— 非递归算法
最新版本：2020/10/21
# r_array[]: 排序数组
# low      : 起始索引
# high     : 结束索引
'''
def QuickSortNonR(r_array, low, high):
    stack = []
    stack.insert(0, low)                       # 头指针入栈
    stack.insert(0, high)                      # 尾指针入栈
    while len(stack) != 0 :                    # 若栈不为空
        high = stack.pop(0)                    # 头指针出栈
        low = stack.pop(0)                     # 尾指针出栈
        piviot = partition(r_array, low, high) 
        if low < piviot - 1:
            stack.insert(0, low)
            stack.insert(0, piviot - 1)
        elif piviot + 1 < high:
            stack.insert(0, piviot + 1)
            stack.insert(0, high)

'''
主 函 数（程序入口）
最新版本：2020/10/21
作    者: ZhaoYiman
'''
if __name__ == '__main__':
    sno = (int)(input("# Please input your student ID: "))
    # sno = 2017012749
    beg_num = sno % 10000

    r_array = random_array(beg_num)
    print ("# Randomly generated array —— Recursion Algorithm: ") 
    print(r_array)
    QuickSort(r_array, 0, len(r_array) - 1)
    print ("# Sorted array —— Recursion Algorithm: ") 
    print(r_array)

    random.shuffle(r_array)         # 将list中的数据次序打乱，不会生成新的列表
    print ("# Randomly generated array —— Non-recursion Algorithm: ") 
    print(r_array)
    QuickSortNonR(r_array, 0, len(r_array) - 1)
    print ("# Sorted array —— Non-recursion Algorithm: ") 
    print(r_array)

4、元胞自动机（Cellular Automata, 简称CA）是一时间和空间都离散的动力系统。查询和阅读下面文献，将给定整数按照规则X（256种）的N代演进的结果。（按学号后两位，女生为XX规则，男生为1XX规则）
https://www.jianshu.com/p/0d09083c7774
https://blog.csdn.net/bcd_not_cbd/article/details/50479952
https://haokan.baidu.com/v?vid=2605717403108257414

'''
函数名称：MakingRule 
函数功能：制定细胞自动机的演变规则 —— 存储结构：字典Dictionary
最新版本：2020/10/22
00110001
['000', '001', '010', '011', '100', '101', '110', '111']
{'111': '0', '110': '0', '101': '1', '100': '1', '011': '0', '010': '0', '001': '0', '000': '1'}
'''
def MakingRule(sno):
    s_rule = (bin((int)(sno[-2:])))[2:].zfill(8)     # zfill()前补零操作   # bin((int)(sno[-2:])) 为 0b110001
    li_rule = []
    for i in range(0, 8):
        li_rule.append((bin(i))[2:].zfill(3))        
    rule = dict([(li_rule[7 - t], s_rule[t]) for t in range(0, 8)])   # 将迭代规则存储到字典中
    return rule

'''
函数名称：CellularAutomata 
函数功能：按照一定的规则验证N代演进结果
最新版本：2020/10/22
'''
def CellularAutomata(N, rule, test_line):
    print("第  0  代：" + test_line)
    for i in range(1, N + 1):
        test_line_new = ''
        test_line_new = test_line_new + rule[test_line[-1:] + test_line[:2]]   # 特殊处理序列首
        for j in range(0, len(test_line) - 2 ):
            if j >= 0 and  j < len(test_line) - 2:
                test_line_new = test_line_new + rule[test_line[j: j + 3]]      # 中间则遍历处理
        test_line_new = test_line_new + rule[test_line[-2:] + test_line[:1]]   # 特殊处理序列尾
        test_line = test_line_new
        print("第",'%2d '%i, "代：" + test_line)

'''
主 函 数（程序入口）
最新版本：2020/10/22
作    者: ZhaoYiman
规    则：(49) = （110001）B，规则即：00110001
测试序列："1100110000000000110011000000000000001100000011000111000000000111"
'''
if __name__ == '__main__':
    sno = input("请输入你的学号：")
    print("本程序中元胞自动机的迭代规则为：")
    rule = MakingRule(sno)      # 制定规则
    print(rule)
    test_line = "1100110000000000110011000000000000001100000011000111000000000111"
    while True:
        N = (int)(input("请输入迭代次数(N>0)："))
        if N <= 0:
            print("请按要求输入合法数值!")
        else: CellularAutomata(N, rule, test_line)