Ece391: Computer System Engineering Homework 4
tải về 27.13 Kb.
|
- Điều hướng trang này:
- A linearly recursive algorithm is one that makes a single recursive call in each branch of the function.
- // A function that returns the minimum element of an array using linear recursion int findMin (int arr [], int n) {
|
ECE391: Computer System Engineering Homework 4 Show that Show that Show that is a constant Find the complexity of the function int selectkth(int a[], int k, int n) { int i, j, mini, tmp; for (i=0; i tmp = a[i]; a[i] = a[mini]; a[mini] = tmp; } } Describe a linearly recursive algorithm for finding the minimum element in an n-element array. A linearly recursive algorithm is one that makes a single recursive call in each branch of the function. - Base case: If the array has only one element, return that element as the minimum. - Recursive case: Compare the first element of the array with the minimum element of the rest of the array (obtained by a recursive call), and return the smaller one as the minimum. // A function that returns the minimum element of an array using linear recursion int findMin (int arr [], int n) { // Base case: if the array has only one element, return it if (n == 1) { return arr [0]; } // Recursive case: compare the first element with the minimum of the rest of the array else { return min (arr [0], findMin (arr + 1, n - 1)); } } This function takes an array and its size as parameters and returns the minimum element of the array. It uses the `min` function from the standard library to compare two integers and return the smaller one. It also uses pointer arithmetic to access the subarray from the second element to the last element by adding one to the array pointer. The size of the subarray is decreased by one in each recursive call. Describe a recursive algorithm for printing all of the permutations of the sequence (1,2,…,n). What is the running time of your algorithm? Describe the output of the following series of stack operations: push(8), push(3), pop(), push(2), push(5), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(), pop(). Describe the output for the following sequence of queue operations: insertFirst(3), insertLast(8), insertLast(9), insertFirst(5), removeFirst(), removeLast(), first(), insertLast(7), removeFirst(), last(), removeLast(). Given a class Ticket below
a). Write a constructor for the class Ticket to assign the default values for name, ID, and birthyear. Name = “NO NAME”; ID = “0000”; Birthyear = 0; b). Write constructor for the class Ticket to assign the new information into the member variables. string new_name; string new_ID; unsigned int new_birthyear; Given a QUEUE of Ticket named Waiting_list as below:
c). Write a function to add a person with the following information into the Waiting list: string my_name = “Nguyen Van A”; string my_ID= “0010”; unsigned int my_birthyear = 1990; d). Write a function to get the information of a person at the front of the Waiting_list. tải về 27.13 Kb. Chia sẻ với bạn bè của bạn:
|