合肥生活安徽新聞合肥交通合肥房產(chǎn)生活服務(wù)合肥教育合肥招聘合肥旅游文化藝術(shù)合肥美食合肥地圖合肥社保合肥醫(yī)院企業(yè)服務(wù)合肥法律

        代寫CS1010S: Advanced Recursion

        時(shí)間:2024-02-24  來(lái)源:合肥網(wǎng)hfw.cc  作者:hfw.cc 我要糾錯(cuò)


        CS1010S: Programming Methodology

        Semester II, 2023/2024

        Mission 4

        Advanced Recursion

        Release date: 16th February 2024

        Due: 22nd February 2024, 23:59

        Required Files

        • mission04-template.py

        Background

        After demonstrating your abilities to Pharaoh Tyro, you were honored with the presti-gious role of bishop within his esteemed team. The anticipation was palpable as you entered his chambers, where Tyro’s eyes sparkled with expectation. With a grand ges-ture, he handed you three scrolls (Your mission tasks), each bearing the royal seal.

        "These," he declared, his voice resonating with authority, "are your inaugural assign-ments as bishop. Execute them diligently and report to me during the upcoming CS1010S class."

        This mission consists of three tasks.

        Task 1: Number of ways to sum to an Integer (3 marks)

        A positive integer n ≥ 2 can be expressed as the sum of a number of positive integers smaller than n. For example:

        2 = 1 + 1

        3 = 1 + 2

           = 1 + 1 + 1

        4 = 1 + 3

           = 2 + 2

           = 1 + 1 + 2

           = 1 + 1 + 1 + 1

        5 = 1 + 4

           = 1 + 1 + 3

           = 2 + 3

           = 1 + 2 + 2

           = 1 + 1 + 1 + 2

           = 1 + 1 + 1 + 1 + 1

        The function num_sum returns the number of ways that an integer can be expressed as the sum of a number of positive integers. From the above examples, it should be clear that:

        >>> num_sum ( 2 )

        1

        >>> num_sum ( 3 )

        2

        >>> num_sum ( 4 )

        4

        >>> num_sum ( 5 )

        6

        Hint: If you grasp the essence of the count change problem, you’ll recognize that this problem is a variation of it. You may want to consider implementing a helper function that model the count change process of this problem. Solving the problem using closed-form formulas are not allowed.

        Task 2: Generalized Pathfinding: Enumerate All Paths (3 marks)

        In Lecture Training 5, you faced a problem where you were required to assist Jon in im-plementing a function, num_of_possible_path(board). This function determined the num-ber of possible paths to move from the starting point "S" to the ending point "E" by either walking (covering 1 step) or jumping (covering 2 steps).

        Now, you encountered a similar challenge. The game no longer restricts the steps to just 1 or 2; instead, it can be any arbitrary number of steps (i.e. 1, 2, 3, ..., n). Your task is to implement an iterative recursive function, num_of_possible_path(board), which calculates the number of possible paths to move from the starting point "S" to the ending point "E" given that there are n possible ways to move at each step.

        You may assume substring(string, start, end, step) function is given.

        Hint: Observe that this problem resembles a count change problem. At each step, you have the choice to move 1 step forward, or 2 steps forward, or 3 steps forward, and so on, up to n steps forward.

        >>> num_of_possible_path ("S##E", 1 )

        1

        >>> num_of_possible_path ("S##E", 2 )

        3

        >>> num_of_possible_path ("S##E", 3 )

        4

        Task 3: Check valid brackets (5 marks)

        Consider a string containing only brackets "(" and ")". A string of brackets is considered valid if:

        • Every opening parenthesis has a corresponding closing parenthesis.

        • Opening and closing parentheses are in the correct order.

        • Each closing parenthesis has a matching opening parenthesis.

        Implement a function, check_valid_brackets(s), that returns True if the string s is valid brackets, and False otherwise.

        Hint: If a string of brackets is valid, it can repeatedly remove the innermost non-nested "()" until it becomes an empty string.

        Subtask 3a: Illustrate Your Problem-Solving Approach

        In Lecture 1, you have learnt the Polya’s Problem Solving Process:

        1. Understand the Problem

        2. Make a Plan (Create a Flowchart, as outlined in Lecture 1 slides)

        3. Do the Plan

        4. Review & Generalize

        Apply the Polya problem-solving methodology, and demonstrate your problem-solving process for Task 3. You are tasked to write out each step, providing insights into your approach and decision-making. This exercise aims to reinforce your understanding and application of the problem-solving methodology.

        Please submit your illustration to coursemology. Note that you must include Step 1 and Step 2 in your illustration; Step 3 and Step 4 are optional. (For an example, please refer to Coursemology -> Workbin -> PolyasProblemSolvingExample.pdf)

        By using the idea of divide and conquer, here are the steps to solve Task 2

        1. Implement an iterative function remove_bracket_pair(s) that takes in a string of brackets. This function iterates through the string from left to right, removing the first occurrence of the brackets pair "()" within the string s, and returns the modified string. You may assume substring(string, start, end, step) function is given.

        >>> remove_bracket_pair (" ()()() ")

        " ()() "

        >>> remove_bracket_pair (" (()()) ")

        " (()) "

        >>> remove_bracket_pair (" ((())) ")

        " (()) "

        >>> remove_bracket_pair (")()")

        ")"

        >>> remove_bracket_pair ("()")

        ""

        >>> remove_bracket_pair (" (())((())) ")

        " ()((())) "

        2. Using the above iterative remove_bracket_pair(s) function, implement a recursive check_valid_brackets(s) that takes in a string of brackets and returns True if the string s is valid brackets, and False otherwise.

        >>> check_valid_brackets ("()")

        True

        >>> check_valid_brackets (" (()) ")

        True

        >>> check_valid_brackets (" ()() ")

        True

        >>> check_valid_brackets (" (()")

        False

        >>> check_valid_brackets (" ())")

        False

        >>> check_valid_brackets (" ())( ")

        False

        Subtask 3b: Execute Your Plan

        1. Implement the iterative function remove_bracket_pair(s).

        2. Implement the recursive function check_valid_brackets(s).

        You may assume substring(string, start, end, step) function is given.

        You are highly encouraged to test your functions with additional test cases.

        Optional: Spiral Maze Iterative Recursively

        Write an iterative recursive function num_of_steps that takes in 4 arguments, the x and y coordinates of ending point, x and y, width of the maze, W and height of the maze, H. The function returns the number of steps to navigate from the bottom-left corner (origin) of the maze to the specified ending point. Please follow the question requirements any closed form formula or pure iterative solution will not be accepted.

        Hint: You will need to iterate until the boundary, then recursively call the function with the new boundary and updated x & y.



        Figure 1: A spiral maze with height 3 and width 3. The number of steps from the origin to the ending point (1, 1) is 8.

        num_of_steps (1 , 1 , 3 , 3 )

        >>> 8

        num_of_steps (0 , 0 , 3 , 3 )

        >>> 0

        num_of_steps (1 , 1 , 3 , 2 )

        >>> 4

        num_of_steps (1 , 3 , 5 , 7 )

        >>>

        Optional: Alternative approach of Task 2

        There are many ways to solve the problem in Task 2. You are encouraged to explore alternative approaches to solve the problem.

        You may assume substring(string, start, end, step) function is given in this task.

        Implement a function, check_valid_brackets_alt(s), that returns True if the string s is valid brackets, and False otherwise.

        Completely Iterative Approach (Easy)

        You can implement the function purely iterative. Please confine your implementation to what you’ve learned from CS1010S thus far.

        Completely Recursive Approach (Challenging)

        You may also implement the function purely recursively.

        Warning: This is a challenging task.

        請(qǐng)加QQ:99515681  郵箱:99515681@qq.com   WX:codehelp 

        掃一掃在手機(jī)打開(kāi)當(dāng)前頁(yè)
      1. 上一篇:代寫ELEC-4840 編程
      2. 下一篇:代寫 Financial Derivatives and Financial
      3. 無(wú)相關(guān)信息
        合肥生活資訊

        合肥圖文信息
        急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計(jì)優(yōu)化
        急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計(jì)優(yōu)化
        出評(píng) 開(kāi)團(tuán)工具
        出評(píng) 開(kāi)團(tuán)工具
        挖掘機(jī)濾芯提升發(fā)動(dòng)機(jī)性能
        挖掘機(jī)濾芯提升發(fā)動(dòng)機(jī)性能
        海信羅馬假日洗衣機(jī)亮相AWE  復(fù)古美學(xué)與現(xiàn)代科技完美結(jié)合
        海信羅馬假日洗衣機(jī)亮相AWE 復(fù)古美學(xué)與現(xiàn)代
        合肥機(jī)場(chǎng)巴士4號(hào)線
        合肥機(jī)場(chǎng)巴士4號(hào)線
        合肥機(jī)場(chǎng)巴士3號(hào)線
        合肥機(jī)場(chǎng)巴士3號(hào)線
        合肥機(jī)場(chǎng)巴士2號(hào)線
        合肥機(jī)場(chǎng)巴士2號(hào)線
        合肥機(jī)場(chǎng)巴士1號(hào)線
        合肥機(jī)場(chǎng)巴士1號(hào)線
      4. 短信驗(yàn)證碼 酒店vi設(shè)計(jì) NBA直播 幣安下載

        關(guān)于我們 | 打賞支持 | 廣告服務(wù) | 聯(lián)系我們 | 網(wǎng)站地圖 | 免責(zé)聲明 | 幫助中心 | 友情鏈接 |

        Copyright © 2025 hfw.cc Inc. All Rights Reserved. 合肥網(wǎng) 版權(quán)所有
        ICP備06013414號(hào)-3 公安備 42010502001045

        主站蜘蛛池模板: 色综合视频一区中文字幕| 精品一区二区三区四区电影| 亚洲综合一区二区三区四区五区| 精品亚洲福利一区二区| 久久精品国产一区二区电影| 最新欧美精品一区二区三区| 日韩一区二区在线观看视频| 成人精品视频一区二区三区不卡 | 亚洲综合无码AV一区二区 | 日韩一区二区精品观看| 3D动漫精品一区二区三区| 亚洲中文字幕无码一区| 精品国产一区二区22| 国产精品亚洲产品一区二区三区| 国产精品成人99一区无码| 亚洲av无码片vr一区二区三区| 色国产精品一区在线观看| 日韩一区二区久久久久久| 国内精品无码一区二区三区| 国产日韩高清一区二区三区| 亚洲一区二区三区免费| 偷拍精品视频一区二区三区| 亚洲爽爽一区二区三区| 一区二区三区在线|日本| 高清一区二区在线观看| 一区视频免费观看| 制服中文字幕一区二区| 狠狠色成人一区二区三区| 久久精品岛国av一区二区无码| 国产视频一区在线观看| 国产精品视频一区二区噜噜 | 国产精品熟女一区二区| 国产激情无码一区二区app| 国产丝袜视频一区二区三区| 伊人久久精品无码av一区| 久久久精品人妻一区二区三区| 久久精品无码一区二区无码| 日韩一区二区三区四区不卡| 国产精品视频免费一区二区三区| 日韩伦理一区二区| 中文字幕亚洲乱码熟女一区二区|