生物信息学算法导论1

线性代数基础

算法练习

Maximum Number

Given a series of numbers, get the maximum one.

Specifications

• INPUT a series (length ranged [1,4096]) of integers ranged [−214,214].
• OUTPUT the maximum one.

Sample

1
3
2
3
3

Code Template

import sys

from typing import Iterable

def my_max(s: Iterable[int]) -> int:
    ... # Your code here

if __name__ == "__main__":
    print(my_max(map(int, sys.stdin)))

Implementation Limitations

You should not use max function. Implement this function using loops and assignments only.

My answer

import sys

from typing import Iterable

def my_max(s: Iterable[int]) -> int:
    max_num = None
    for num in s:
        if max_num is None or num > max_num:
            max_num = num
    return max_num

if __name__ == "__main__":
    print(my_max(map(int, sys.stdin)))

算法解释

1. 定义一个max_num来作为迭代用的变量
2. 对可迭代的s对象进行遍历，如果遍历到比max_num更大的数，则迭代max_num

Bubble Sort

Specifications

• INPUT A list (length ranged [0,10000]) of integers ranged [−214,214] that can be read by the json module of Python standard library.
• OUTPUT A list of sorted integers serialized by the json module of Python standard library.

Sample

[-22, -6, -7, 80, 62, 79, 21]
[-22, -7, -6, 21, 62, 79, 80]

Code Template

import json
import sys
from typing import List
def bubble_sort(l: List[int]) -> None:
    """
    In-Place Selection Sort
    
    :param l: The unsorted input array. IT WILL BE MUTATED INSIDE THE FUNCTION.
    """
    ... # Your code here.
if __name__ == "__main__":
    l = list(json.load(sys.stdin))
    bubble_sort(l)
    json.dump(l, sys.stdout)

Implementation Limitations

The bubble sort algorithm should be IN PLACE without requesting for more memories.

My answer

import json
import sys
from typing import List

def bubble_sort(l: List[int]) -> None:
    n = len(l)
    for i in range(n):
        for j in range(0, n - i - 1):
            if l[j] > l[j + 1]:
                l[j], l[j + 1] = l[j + 1], l[j]

if __name__ == "__main__":
    l = list(json.load(sys.stdin))
    bubble_sort(l)
    json.dump(l, sys.stdout)

算法解释

冒泡排序

1. 对相邻两个对象进行比较，如果前面的比后面的大，则进行换位
2. 当遍历换位完整个列表时，再遍历一次判断是否存在前者大于后者的元素，如果没有，则返回列表

Selection Sort

Selection sort is one of the most basic sorting algorithms in computer science. It has an O(n2) complexity so is not commonly used to sort large arrays. The algorithm of selection sort is simple: It iterates the array and finds the smallest (or largest, depending on the sorting order) value, and pushes the value to a sorted sublist of items which is built up from left to right at the front. It repeatedly iterates the array unless there is no element left.

Specifications

• INPUT A JSON-encoded list (length ranged [0,10000]) of integers ranged [−214,214].
• OUTPUT A JSON-encoded list of sorted integers.

Sample

[-22, -6, -7, 80, 62, 79, 21]
[-22, -7, -6, 21, 62, 79, 80]

Code Template

import json
import sys
from typing import List

def selection_sort(l: List[int]) -> None:
    """
    In-Place Selection Sort
    
    :param l: The unsorted input array. IT WILL BE MUTATED INSIDE THE FUNCTION.
    """
    ... # Your code here.

if __name__ == "__main__":
    l = list(json.load(sys.stdin))
    selection_sort(l)
    json.dump(l, sys.stdout)

Implementation Limitations

The selection sort algorithm should be IN PLACE without requesting for more memories. For example, the following selection-sort-like algorithm can also sort arrays but is NOT considered correct:

from typing import List

def selection_sort_not_inplace(l: List[int]) -> List[int]:
    retl = []
    while l:
        min_l = min(l)
        l.remove(min_l)
        retl.append(min_l)
    return retl

My answer

import json
import sys
from typing import List

def selection_sort(l: List[int]) -> None:
    n = len(l)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if l[j] < l[min_idx]:
                min_idx = j
        l[i], l[min_idx] = l[min_idx], l[i]
if __name__ == "__main__":
    l = list(json.load(sys.stdin))
    selection_sort(l)
    json.dump(l, sys.stdout)

算法解释

1. 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
2. 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换