題意：

python算法的考察课锌，主要分為三個任務（task1厨内，task2，task3）产镐，每個任務包含三個小問（partA隘庄，partB，partC）

解析：

task1-partA：按步長刪除字符串的字符癣亚，將剩余字符重新組合輸出丑掺。例如 decode('#P#y#t#h#o#n#',1)，輸出‘Python’

Decode 部分創(chuàng)建新的空字符串new_str=''述雾，每次向空字符串后面添加有效的字符最后返回new_str即可

task1-partA算法思想

task1-partB：計算特定字符在字符串中出現(xiàn)的次數(shù)

Pattern_count 部分進行字符串匹配街州，找到有效字符串后， 讓 count 加 1

task1-partB算法思想

task1-partC：確定輸入字符串是否為回文（回文順讀與倒讀都一致的字符串玻孟，如abcdcba）

Palindrome 部分先去除無效字符唆缴，再將過濾后的新字符串中的英文字母全部轉(zhuǎn)化為小寫字母，再進行 forward 和 backward 的匹配

task1-partC

task2-partA：嵌套列表表示有至少n個朋友的輸出黍翎，例如clayton_list = [ [1,2,3], [0,3], [0,4], [0,1], [2] ]面徽，Calling popular(clayton list,2) returns [0,1,2,3].其中clayton_list表示0和1、2匣掸、3是朋友趟紊，1和0、3是朋友碰酝，2和0霎匈、4是朋友，3和0送爸、1是朋友铛嘱，4和2是朋友，當n=2時袭厂，輸出為[0,1,2,3]表示0墨吓、1、2纹磺、3至少都有兩個朋友

對于 adjacency list 表達法肛真，對于每一個 vertex,其對應的 list 的長度就是朋友的數(shù)目，所以只需數(shù)一數(shù)每一個 list 的長度即可

task2-partA

task2-partB：確定兩個人是否只有一個分離程度：即兩個人無論是不是朋友爽航，但是至少有一個朋友是共同的

對于 adjacency matrix 表達法蚓让，輸入矩陣一定是方陣，即 x y 方向矩陣的長度是相等的讥珍。

（1）通過看矩陣的大小來確定總?cè)藬?shù)历极；

（2）判斷通過矩陣 matrix[person1][person2]的數(shù)值來判斷 1 和 2 是不是朋友（0 代表不是朋友，1 代表是朋友）衷佃；

（3）遍歷person1的朋友圈matrix[person1][：]趟卸，去判斷person1的朋友是不是person2的朋友。

task2-partB

task2-partC：確定一個人是否有兩個朋友也是彼此的朋友

? (1)? 計算 person 的朋友數(shù)目（num_friend）并判斷是否大于 2氏义；

（2）如果朋友數(shù)目大于 2锄列，記錄 person 的朋友是誰（用 index 記錄）

（3）最后，判斷 person 的朋友們有沒有互相是朋友

task2-partC

task3-partA：寫一個函數(shù)將給定的手牌分為四套惯悠，四個套字母順序為梅花邻邮，方塊，紅桃克婶，黑桃

先用冒泡排序?qū)ψ帜疙樞驈男〉酱笈帕型惭希賹⑼蛔帜傅呐菩头胚M同一個 list 里面

task3-partA

task3-partB：寫一個函數(shù)來確定給定的手是否是同花。 在撲克中情萤，同花是包含五張同一套的牌鸭蛙。

直接判斷花色是否相等即可

task3-partB

task3-partC：確定給定的手牌是否是包含五張連續(xù)的牌

先用冒泡排序?qū)?shù)字牌從小到大排列，再計算相鄰兩張牌的差值是否為 1筋岛，如果一直為 1娶视，那就是順子

task3-partC

涉及知識點：

python字符串處理，遍歷睁宰，list用法肪获，冒泡排序，圖的矩陣表示方法

更多可加微信撩騷

FIT1045 Algorithms and programming in Python, S2-2019

Assignment 1 (value 10%)

Due: Friday 30th August 2019, 11:55 pm.

Objectives

The objectives of this assignment are:

? To demonstrate the ability to implement algorithms using basic data structures and operations on them.

? To gain experience in designing an algorithm for a given problem description and implementing that

algorithm in Python.

Submission Procedure

1. Save your files into a zip file called yourStudentID yourFirstName yourLastName.zip

2. Submit your zip file containing your solution to Moodle.

3. Your assignment will not be accepted unless it is a readable zip file.

Important Note: Please ensure that you have read and understood the university’s policies on plagiarism and collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. You will be required to agree to these policies when you submit your assignment. A common mistake students make is to use Google to find solutions to the questions. Once you have seen a solution it is often difficult to come up with your own version. The best way to avoid making this mistake is to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel free to ask for assistance on Moodle, ensuring that you do not post your code.

Marks:This assignment will be marked both by the correctness of your code and by an interview with your lab demonstrator, to assess your understanding. This means that although the quality of your code (commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write clean code so that it is easier for you to understand and explain. This assignment has a total of 12 marks and contributes to 10% of your final mark. For each day an assignment is late, the maximum achievable mark is reduced by 10% of the total. For example, if the assignment is late by 3 days (including weekends), the highest achievable mark is 70% of 12, which is 8.4. Assignments submitted 7 days after the due date will normally not be accepted. Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable to explain your code via a code walk-through in the assessment interview. Readable code is the basis of a convincing code walk-through.

Task 1: Strings (3.5 Marks)

Create a Python module called strings.py. Within this module implement the following three tasks. For this module you may not use the Python sequence method s.count(x).

Part A: Code Breaker (1 Mark)

Write a function decode(string, n) that takes in an encoded message as a string and returns the decoded message.

Input: a string string and a positive integer n.

Output: the decoded string. The string is decoded by discarding the first n characters from the input string, keeping the next n characters, discarding the next n characters, and so on, until the input string is exhausted. There is no guarantee at which point in the decoding (keep or discard) the string will be exhausted. There is no guarantee that the length of string will be a multiple of n.

Examples

a) Calling decode(‘#P#y#t#h#o#n#’, 1) returns ‘Python’.

b) Calling decode(‘AxYLet1x3’s T74codaa7e!’, 3) returns ‘Let’s code!’.

Part B: Pattern Finder (1 Mark)

Write a function pattern count(string, pat) that counts how many times a pattern occurs within a text.

Input: a string string and a string pat, both comprising both upper and lower case alphanumeric and non-alphanumeric characters.

Output: an integer count of the number of times pat occurs within string. The count is case sensitive. (See Example b.)

Examples

a) Calling pattern count(‘bcabcabca’, ‘a(chǎn)bc’) returns 2.

b) Calling pattern count(‘a(chǎn)aaa’, ‘a(chǎn)a’) returns 3.

c) Calling pattern count(‘A long time ago in a galaxy far, far away...’, ‘a(chǎn)’) returns 8.

d) Calling pattern count(‘If you must blink, do it now.’, ‘code’) returns 0.

Part C: Palindromes (1.5 Marks)

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Write a function palindrome(string) that determines whether or not a given string is a palindrome. In order to receive full marks, the function must determine whether the alphanumerical characters create a palindrome (see Examples).

Input: a string string comprising both upper and lower case alphanumeric and non-alphanumeric characters.

Output: a boolean, True if the string when converted to lower case alphanumeric characters is a palindrome; otherwise False.

Examples

a) Calling palindrome(‘RacecaR’) returns True because ‘RacecaR’ reads the same backwards as forwards.

b) Calling palindrome(‘66racecar77’) returns False because ‘66racecar77’ does not read the same backwards as forwards.

c) Calling palindrome(‘Racecar’) returns True because ‘racecar’ reads the same backwards as forwards.

d) Calling palindrome(‘Madam, I’m Adam’) returns True because ‘madamimadam’ reads the same backwards as forwards.

e) Calling palindrome(‘#4Satire: Veritas4’) returns True because ‘4satireveritas4’ reads the same backwards as forwards.

Marking Guide (total 3.5 marks)

Marks are given for the correct behavior of the different functions:

(a) 1 mark for decode.

(b) 1 mark for pattern count.

(c) 0.5 marks if palindrome can correctly identify that a string with no processing is a palindrome (see Examples a and b), 1.5 marks if palindrome can correctly identify that a string when converted to lower case alphanumeric characters is a palindrome (see Examples c, d, and e).

Task 2: Friends (4.5 Marks)

You have been employed by Monash to analyse friendship groups on campus. Individuals have been allocated a number between 0 and the number of people on campus (minus one), and their friendships have been recorded as edges between numbered vertices. We assume friendships are always bi-directional. Monash has implemented this graph in a Python-readable format as both an adjacency matrix and an adjacency list. Create a Python module called friends.py. Within this module implement the following three tasks. Ensure you follow the inputs for each function correctly - one function takes an adjacency list, two functions take an adjacency matrix.

Part A: Popular (1.5 Marks)

Write a function popular(graph list, n) that returns a list of people who have at least n friends. Each person is identified by the number of their vertex.

Input: a nested list graph list that represents a graph as an adjacency list, that models the friendships at Monash; and a non-negative integer n.

Output: a list of integers, where each integer is a person with at least n friends. If no person has at least n friends, return an empty list. The list may be in any order.

Examples

clayton_list = [ [1,2,3], [0,3], [0,4], [0,1], [2] ]

The example graph clayton list is provided for illustrative purpose. Your implemented function must be able to handle arbitrary graphs in list form.

a) Calling popular(clayton list,2) returns [0,1,2,3].

b) Calling popular(clayton list,3) returns [0].

c) Calling popular(clayton list,0) returns [0,1,2,3,4].

Part B: Friend of a Friend (1.5 Marks)

Write a function foaf(graph matrix, person1, person2) that determines whether two people have exactly one degree of separation: that is, whether two (distinct)1 people are not friends, but have at least one friend in common.

Input: a nested list graph matrix that represents a graph as an adjacency matrix, that models the friendships at Monash; an integer person1, and an integer person2, where 0 ≤ person1, person2 < number of people on campus, and person1 6= person2.

Output: a boolean, True if the two people are not friends and they have at least one friend in common; otherwise False.

Examples

clayton_matrix = [ [0,1,1,1,0],

[1,0,0,1,0],

[1,0,0,0,1],

[1,1,0,0,0],

[0,0,1,0,0] ]

The example graph clayton matrix is provided for illustrative purpose. Your implemented function must be able to handle arbitrary graphs in matrix form.

a) Calling foaf(clayton matrix,0,4) returns True as 0 and 4 are both friends with 2.

b) Calling foaf(clayton matrix,0,3) returns False as 0 and 3 are friends directly.

c) Calling foaf(clayton matrix,1,4) returns False as 1 and 4 have no friends in common.

Part C: Society (1.5 Marks)

Write a function society(graph matrix, person) that determines whether a person has two friends who are also friends with each other.

Input: a nested list graph matrix that represents a graph as an adjacency matrix, that models the friendships at Monash; and an integer person, where 0 ≤ person < number of people on campus.

Output: a boolean, True if person has at least two friends who are also friends with each other; otherwise False.

Examples

a) Calling society(clayton matrix,0) returns True as 1 and 3 are both friends with 0.

b) Calling society(clayton matrix,2) returns False as 2 is friends with 0 and 4, but 0 and 4 are not friends with each other.

Marking Guide (total 4.5 marks)

Marks are given for the correct behavior of the different functions:

(a) 1.5 marks for popular.

(b) 1.5 marks for foaf.

(c) 1.5 marks for society.

Task 3: Cards (4 Marks)

A friend of yours is developing a prototype for a website on which people can play poker. They have contacted you to help them implement some of the project’s backend: specifically, they would like some help telling what kind of hand a player has played. You have agreed to implement four functions to assist them. In the backend, your friend has decided to represent cards as tuples comprising an integer and a string: (rank, suit). For example, the seven of clubs would be represented as (7, ‘C’). As this is a prototype, your friend has told you that no face cards will be used (that is, rank is always an integer, where 2 ≤ rank ≤ 10, unless otherwise specified). There are four suits, with the following string representations: clubs: ‘C’, diamonds: ‘D’, hearts: ‘H’, spades: ‘S’. As this is poker, which is only played with one deck of cards, there will never be duplicates, and each hand will contain exactly five cards. Create a Python module called cards.py. Within this module implement the following four tasks. For this module you may not use the Python inbuilt function sorted() or the Python method list.sort().

Part A: Suits (1 Mark)

Write a function suits(hand) that sorts a given hand into the four suits. As there is no standard ranking of suits in poker, we will order alphabetically: clubs, diamonds, hearts, spades.

Input: a list hand containing five cards.

Output: a nested list containing four lists of cards, with each internal list corresponding to a suit. If there are no cards of that suit in the hand, the internal list for that suit is empty. Cards may be in any order within their suit-list.

Part B: Flush (1 Mark)

Write a function flush(hand) that determines whether a given hand is a flush. In poker, a flush is a hand that contains five cards of the same suit.

Input: a list hand containing five cards.

Output: a boolean, True if all five cards in hand are the same suit, False if not.

Part C: Straight (2 Marks)

Write a function straight(hand) that determines whether a given hand is a straight. In poker, a straight is a hand that contains five cards of sequential rank. The cards may be of different suits. Your friend has asked you an additional favour: they would like to use this function in various other games they may implement in the future, so instead of checking for a five-card straight, they would like you to check for an n card straight, where n is the number of cards in the hand. Like in poker, the cards may be of different suits.

Input: a list hand containing at least three cards, where each card may have a rank of some number greater than zero.

Output: a boolean, True if the ranks of the cards in hand may be ordered into an unbroken sequence with no rank duplicated, False if not.

Examples

a) Calling suits([(4,‘C’),(8,‘H’),(3,‘C’),(2,‘D’),(8,‘C’)]) returns [[(4,‘C’),(3,‘C’),(8,‘C’)], [(2,‘D’)], [(8,‘H’)], []]. As there are multiple clubs, the clubs cards may be in any order within their internal list.

b) Calling flush([(4,‘D’),(8,‘D’),(3,‘D’),(2,‘D’),(10,‘D’)]) returns True.

c) Calling flush([(4,‘C’),(8,‘H’),(3,‘C’),(2,‘D’),(8,‘C’)]) returns False.

d) Calling straight([(4,‘C’),(2,‘D’),(5,‘S’),(6,‘H’),(3,‘D’)]) returns True.

e) Calling straight([(2,‘C’),(3,‘D’),(4,‘S’),(5,‘H’),(5,‘D’)]) returns False.

f) Calling straight([(2,‘C’),(3,‘D’),(4,‘S’),(5,‘H’),(7,‘D’)]) returns False.

g) Calling straight([(12,‘C’),(13,‘D’),(11,‘D’)]) returns True as the ranks of the cards form an unbroken sequence, [11,12,13], with no rank duplicated.

Marking Guide (total 4 marks)

Marks are given for the correct behavior of the different functions:

(a) 1 mark for suits.

(b) 1 mark for flush.

(c) 1 mark for straight if it is able to handle a normal poker five-card hand with card ranks between 2 and

10 inclusive (see Examples d, e, and f); 2 marks for straight if it is able to handle an arbitrarily large hand with arbitrary ranks (see Example g).