1 in 6 The University of Hong Kong COMP1117B Computer Programming Assignment 3 Deadline date: Apr 8 11:59 pm Reminder: This assignment involves some console input/output. You are reminded that the VPL system on HKU Moodle evaluates your program with a full score under the condition that your program output is the EXACT MATCH of the expected output. In other words, any additional or missing space character, tab character, newline character, etc. will be treated as errors during the evaluation of your program. Also, you are advised to make more test cases on your own for testing your program. Question 1 (35%): Exist or not Task Description: In this task, we will develop a program to detect whether a target number is the sum of k elements in the given list numbers (note that the elements in numbers are positive integers and we input the integers one by one, one integer at a time, and terminated by -1). Please carefully read the below cases for a better understanding. Case 1 INPUT: 1 2 8 9 39 92 161 -1 209 3 OUTPUT: Yes Explanation: It print “Yes” because there are 3 numbers in the given list that sum up to 209 (9 + 39 + 161) 2 in 6 Case 2 INPUT: 32 392 93022 349895 -1 1280298402 2 OUTPUT: No Explanation: It print “No” because we cannot find 2 numbers in the given list [32, 293, 93022, 349895] to sum up to 1280298402 Given program 1. number = int(input()) 2. numbers = [] 3. while number != -1: 4. numbers.append(number) 5. number = int(input()) 6. target = int(input()) 7. k = int(input()) 8. 9. 10. def isExist(# define parameters): 11. # your implementation 12. 13. 14. if isExist(# input the appropriate variables): 15. print(“Yes”) 16. else: 17. print(“No”) 1. You are expected to use recursion algorithm to solve this problem. It will have a 20% deduction if your submission is not a recursion solution. 2. Hint: If the current number x should be included in finding the target number, then summing up k elements to find the target will be equivalent to summing up [k-1] elements to find [target -x]. Similarly, try to figure out the recurrence relationship for the situation where x should not be included in the process. 3. Please read the given code carefully for better understanding. 4. You can start the recursion on is_exist(), or you can define another recursive function and use is_exist() to call it. You may define as many functions as you need but you are not required to do so. 5. You must show the output of the function using the print() provided above. 6. You are not allowed to change any line of code in the given program. 7. Make sure your program can handle input range 1 < k < 6, where k is a positive integer. For example, in the above case ([1, 2, 8, 9, 39, 92, 161], 109, 3), the k is 3. 8. You can use any built-in functions in Python. 3 in 6 Question 2 (65%): Result-guessing game Task Description: Gary and Tom are playing a result-guessing game together. Overall, this game is simple, the judge will give a positive integer to the participants, and then the participants need to judge whether the given number list is fulfilling the requirements (below will have a detailed requirement description about the requirement). The winner will be the one who can give the fastest and correct answer. However, Tom is not good at logic, which makes his winning chance low. Therefore, in this task, please write a program to help Tom to win this game. Overview of the expected program: Overview of the requirements: 4 in 6 Count jumping scheme The expected input of this module is a positive integer. Assuming we want to go to a destination that needs to jump number step(s). Here is the question: if we can only jump 1 or 2 step(s) for each time, how many possible ways are available to jump to the destination Example: number = 3 The output will be 3 because there is total 3 schemes for jumping 3 steps. 1st scheme: jump 1 step + jump 1 step + jump 1 step 2ed scheme: jump 1 step + 2 steps 3rd scheme: jump 2 steps + 1 step Check whether a number is a lucky number The input of this module will be a positive Integer and the output will be a Boolean. Note that the lucky number is determined by the below rule: abs((The most frequent digit * its frequency) – (the least frequent digit * its frequency)) If the number resulting from the above formula ends with 6, then it is considered as a lucky number. Note 1) If there are equal frequencies among the digits in the test cases, then the larger digit will be used for calculation. 2
) The least frequency does not include zero. Example: number = 7398827232 There are three 2’s, which is the most frequent digit in the number; there is only one 9 in the number. By applying the formula above, we’ll have abs((2*3)-(9 *1)) = abs(-3) = 3. This number does not end with 6, so it is not a lucky number. number = 330 There are two 3’s, which is the most frequent digit in the number; there is only 1 0’ in the number. By applying the formula above, we’ll have abs((3*2)-(0*1)) = abs(6) = 6. This number ends with 6, so it is a lucky number. For the whole process For examples: INPUT: number = 500 OUTPUT: “No” The number will be first proceeded by the count jumping scheme module, and the result will be 2255915161619363308725126950360720720460113249137581905886388664184746277386 5 in 6 86883405015987052796968498626. It’s not a lucky number, therefore the program will print “No”. INPUT: number = 18 OUTPUT: “Yes” The number will be first proceeded by the count jumping scheme module, and the result will be 4181. It’s a lucky number, therefore, the program will print “Yes”. Given program 1. def number_to_digitLis_reversed_order(num): 2. digits = [] 3. while num != 0: 4. digits.append(num % 10) 5. num //= 10 6. return digits 7. 8. 9. def numbers_to_digitLis_original_order(num): 10. reversed_digits = number_to_digitLis_reversed_order(num) 11. n = len(reversed_digits) 12. original_digits = [] 13. for i in range(0, n): 14. original_digits.append(reversed_digits[n-i-1]) 15. return original_digits 16. 17. 18. def is_lucky_number (num): 19. digits = numbers_to_digitLis_original_order(num) 20. # your implementation 21. 22. 23. def count_jumping_scheme(num): 24. # your implementation 25. 26. 27. number = int(input()) 28. num_of_schemes = count_jumping_scheme(number) 29. if is_lucky_number(num_of_schemes): 30. print(“Yes”) 31. else: 32. print(“No”) N.B. 1. Make sure your program can handle input 1 < num < 1000. 2. You can use any built-in functions in Python. 3. Try to define your own functions for each of the modules to make the flow clear. 4. Please read the given code carefully for better understanding. 5. You must show the output of the function using the print() provided above. 6. You are not allowed to change any line of code in the given program. 7. You can use any built-in functions in Python. 6 in 6 Appendix Important Notes: Your program must follow the formats of the sample inputs/outputs strictly. We will grade your programs with another set of test cases (i.e., not limited to the sample test cases presented in this document/VPL). Policy on “Plagiarism” according to the General Office: Plagiarism is a very serious academic offence. Students should understand what constitutes plagiarism, the consequences of committing an offence of plagiarism, and how to avoid it. Definition of Plagiarism: - As defined in the University's Regulations Governing Conduct at Examinations, plagiarism is "the unacknowledged use, as one's own, of work of another person, whether or not such work has been published.", or put it simply, plagiarism is copying (including paraphrasing) the work of another person (including an idea or argument) without proper acknowledgement. - In case of queries on plagiarism, students are strongly advised to refer to "What is Plagiarism”. If a student commits plagiarism, with evidence after investigation, no matter whether the student concerned admits or not, a penalty will be imposed: - First Attempt: if the student commits plagiarism (in an assignment/test of a CS course) for the first time in his/her entire course of study, the student shall be warned in writing and receive zero mark for the whole assignment or the whole test; if the student does not agree, s/he can appeal to the BEng(CompSc) Programme Director within a week; - Subsequent Attempt: if the student commits plagiarism more than once in higher course of study, the case shall be referred to the Programme Director for consideration. The Programme Director shall investigate the case and consider referring it to the University Disciplinary Committee, which may impose any of the following penalties: a published reprimand, suspension of study for a period of time, fine, or expulsion from the University. Both the student who copies other's work and the student who offers his/her work for copying shall be penalized. Teachers should report plagiarism cases to the General Office for records and the issuing of warning letters.