C# For Dummies
Chapter 7. Arrays
1. Write a program, which creates an array of 20 elements of type integer and initializes each of the elements with a value equals to the index of the element multiplied by 5. Print the elements to the console.Guidelines: Use an
int[] array and afor loop.Solution:
Link
2. Write a program, which reads two arrays from the console and checks whether they are equal (two arrays are equal when they are of equal length and all of their elements, which have the same index, are equal).
Guidelines: Two arrays are equal if they have the same value for the length and the values for their elements. You can check for the second condition using a for-loop
Solution:
Link
3. Write a program, which compares two arrays of type char lexicographically (character by character) and checks, which one is first in the lexicographical order.
Guidelines: In lexicographic order the elements are compared one by one starting from the very left. If the elements are not the same, the array, whose element is smaller (comes earlier in the alphabet), comes first. If the elements are equal, the next character is compared. If the end of one of the arrays is reached, without finding different elements, the shorter array is the smaller (comes earlier lexicographically). If all elements are equal, the arrays are equal
Solution:
Link
4. Write a program, which finds the maximal sequence of consecutive equal elements in an array.
E.g.: {2, 1, 1, 2, 3, 3, 2, 2, 2, 1} à {2, 2, 2}.
à {2, 2, 2}.
Guidelines: Scan the array from left to right. Every time when the current number is different from the one before it, a new sequence starts. If the current element is equal to the one before it, it is a continuation of the same sequence. So, if we keep the index of the start position of the current sequence (in the beginning it is 0) in
start and the length of the current sequence (in the beginning it is 1) in len, we can find all sequences of equal elements and their lengths. We can easily keep the shortest one in two additional variables – bestStart and bestLen.Solution:
Link
5. Write a program, which finds the maximal sequence of consecutively placed increasing integers.
Example: {3, 2, 3, 4, 2, 2, 4} à {2, 3, 4}.
Guidelines: This exercise is very similar to the previous one, but we have a continuation of the current sequence when the next element is bigger.
Solution:
Link
6. Write a program, which finds the maximal sequence of increasing elements in an array
arr[n]. It is not necessary the elements to be consecutively placed. Example: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} à {2, 4, 6, 8}.
Упътване: Guidelines: We can solve the problem with two nested loops and one more array
len[0…n-1]. In the array len[i] we can keep the length of the longest consecutively increasing sequence, which starts somewhere in the array (it does not matter where exactly) and ends with the element arr[i]. Therefore len[0]=1, len[x] is the maximal sum max(1 + len[prev]), where prev < x and arr[prev] < arr[x]. Following the definition, we can calculate len[0…n-1] with two nested loops: the outer loop will iterate through the array from left to right with the loop variable x. The inner loop will iterate through the array from the start to position x-1 and searches for the element prev with maximal value of len[prev], where arr[prev] < arr[x] . After the search, we initialize len[x] with 1 + the biggest found value of len[prev] or with 1, if such a value is not found. The described algorithm finds the lengths of all maximal ascending sequences, which end at each of the elements. The biggest one of these values is the length of the longest increasing sequence. If we need to find the elements themselves, which compose that longest sequence, we can start from the element, where the sequence ends (at index
x), we can print it and we can search for a previous element (prev). By definition prev < x and len[x] = 1 + len[prev] so we can find prev with a for-loop from 1 to x-1. After that we can repeat the same for x=prev. By finding and printing the previous element (prev) many times until it exists, we can find the elements, which compose the longest sequence in reversed order (from the last to the first).Solution:
Link
7. Write a program, which reads from the console two integer numbers N and K (K < N) and array of N integers. Find those K consecutive elements in the array, which have maximal sum.
Guidelines: Find in Internet information about "Selection sort" and its C# implementations. Briefly the idea is to find the smallest element and to place it at position 0 (through swapping) then to find the smallest number excluding the first and place it at position 1 and so on, until the entire array is arranged in ascending order.
Solution:
Link
8. Sorting an array means to arrange its elements in an increasing (or decreasing) order. Write a program, which sorts an array using the algorithm "
selection sort".Guidelines: Find in Internet information about "Selection sort" and its C# implementations. Briefly the idea is to find the smallest element and to place it at position 0 (through swapping) then to find the smallest number excluding the first and place it at position 1 and so on, until the entire array is arranged in ascending order.
Solution:
Link
9. Write a program, which finds a subsequence of numbers with maximal sum. E.g.: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} à 11
Guidelines: There are two ways to solve this problem. The first way is to use brute force method, which in this case means that using two nested loops we check every possible start and end and its corresponding sum.
The second way is to use one loop through the array to scan it from left to right and sum the elements. Once we get a negative sum, we can restart summing from the next element. Think why this is correct! At each step we check if the current sum is greater than the current max.
Solution:
Link
10. Write a program, which finds the most frequently occurring element in an array. Example: {4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3} à 4 (5 times).
Guidelines: This exercise can be solved in a couple of ways. One of them is the following: get the first number and check how many times it is repeated in the array and store this number in a variable. After a repeated number is found we change its value to
int.MinValue. Then pass to the next number and do the same with it. The current number is remembered if its occurrences are maximal. As you may guess, when a number equal to int.MinValue is found (already processed number) we should skip it. Another solution is to sort the numbers in ascending order and then the elements with same value will be placed next to each other. So, basically we then find the longest sequence of neighbor equal elements.
Solution:
Link
11. Write a program to find a sequence of neighbor numbers in an array, which has a sum of certain number S. Example: {4, 3, 1, 4, 2, 5, 8}, S=11 à {4, 2, 5}.
Guidelines: This exercise can be solved with two nested loops. The first loop assigns a starting index. The second loop sums the elements from the starting index to the right until this partial sum reaches or is greater than S. If the sum is equal to S, we will remember the starting index (from the first loop) and the ending index (from the second loop).
If all numbers are positive, there is a much faster algorithm. We sum all numbers from left to the right, starting from zero. If the current sum becomes greater than S during the summation, we remove the leftmost number in the sequence and we subtract it from the sum. If the current sum is still greater than S, we remove the next leftmost number and do that until the current sum becomes smaller than S. When the sum becomes smaller than S we add the next number on right. If we find a sum equal to S, we print the sum and the sequence to the console. So this solution uses just with one scan through the elements in the array.
Solution:
Link
12. Напишете програма, която създава следните квадратни матрици и ги извежда на конзолата във форматиран вид. Размерът на матриците се въвежда от конзолата.
Example for
(4,4):
Guidelines: a), b), c) Think about appropriate ways for iterating through the matrices with two nested loops.
d) We can start from (0, 0) and go down N times. Therefore, go to the right N-1 times, after that up N-1 times, after that left N-2 times, after that down N-2 times and etc. At each iteration we place the next number in a sequence 1, 2, 3, …, N in the cell, which we are leaving.
Solution:
Link 12a
Link 12b
Link 12c
Link 12d
13. Write a program, which creates a rectangular array with size of
n by m elements. The dimensions and the elements should be read from the console. Find a platform with size of (3, 3) with a maximal sum.Guidelines: Look at the previous solution.
Solution:
Link
14. Write a program, which finds the longest sequence of equal string elements in a matrix. A sequence in a matrix we define as a set of neighbor elements on the same row, column or diagonal.
Guidelines: Check every element in a diagonal line, a row and a column until you get a sequence. If you get a sequence, check whether this sequence is longer than the currently longest sequence.
Solution:
Link
15. Write a program, which creates an array containing all Latin letters. The user inputs a word from the console and as result the program prints to the console the indices of the letters from the word.
Guidelines: We can solve this problem with two nested loops (one for the words and one for the letters of the current word). There is a solution without using an array: we can calculate the index of a given uppercase Latin letter ch using the expression:
(int) ch – (int) 'A'.Solution:
Link
16. Write a program, which uses a binary search in a sorted array of integer numbers to find a certain element.
Guidelines: Find on the Internet information about the algorithm "binary search". Note that binary search works only on sorted arrays.
Solution:
Link
17. Write a program, which sorts an array of integer elements using a "merge sort" algorithm.
Guidelines: Find on the Internet information about the algorithm "merge sort" and its implementations in C#. It is a bit complicated to write merge sort efficiently. You can have 3 preallocated arrays when merging arrays: two arrays for keeping the numbers for merging and а result array. Thus you will never allocate new arrays during the algorithm’s execution. The arrays will be allocated just once at the start and you will just change their purpose (swap them) during the algorithm execution.
Solution:
Link
18. Write a program, which sorts an array of integer elements using a "quick sort" algorithm.
Guidelines: Find information about the "quick sort" algorithm in Internet and its C# implementations. It can be best implemented by using recursion. Generally at each step you choose an element called pivot and reorder the array into two sections: at the left side move all elements ≤ pivot and at the right side move all elements > pivot. Finally run the quicksort algorithm recursively over the left and the right sides.
Solution:
Link
19. Write a program, which finds all prime numbers in the range [1…10,000,000].
Guidelines: Find on the Internet information about "The sieve of Erathostenes" (you have probably heard about it in math classes in high-school).
Solution:
Link
20. Write a program, which checks whether there is a subset of given array of N elements, which has a sum S. The numbers
N, S and the array values are read from the console. Same number can be used many times. Example: {2, 1, 2, 4, 3, 5, 2, 6}, S = 14 à yes (1 + 2 + 5 + 6 = 14)
Guidelines: Generate all possible sums this way: take all the numbers and mark them as "possible sum". Then take every number
ko, k2, …, kn-1 and for each already marked "possible sum" p, mark as possible the sum p+ki. If at some step you get S, a solution is found. You can keep track of the "possible sums" either in a bool[] array possible[], where each index is a possible sum, or in a more complex data structure like Set. Once you have possible[S] == true, you can find a number ki such that possible[S-ki] == true, print ki and subtract it from S. Repeat the same to find the next ki and print and subtract is again, until S reaches 0. Another algorithm: generate all possible subsets of the numbers by a
for-loop from 0 to 2N-1. If we have a number p, take its binary representation (which consists of exactly N bits) and sum the numbers that correspond to 1 in the binary representation of p (with a nested loop from 0 to N-1). Thus all possible sums will be generated and if some of them is S, it can be printed. Note that this algorithm is slow (needs exponential time and cannot run for 100 or 1000 elements). It also does not allow using the same array element twice in the sum.Solution:
Link
21. Write a program which by given N numbers, K and S, finds K elements out of the N numbers, the sum of which is exactly S or says it is not possible.
Example: {3, 1, 2, 4, 9, 6}, S = 14, K = 3 à yes (1 + 2 + 4 = 14)
Solution:
Link
22. Write a program, which reads an array of integer numbers from the console and removes a minimal number of elements in such a way that the remaining array is sorted in an increasing order.
Example: {6, 1, 4, 3, 0, 3, 6, 4, 5} à {1, 3, 3, 4, 5}
Guidelines: Use dynamic programming to find the longest increasing sub-sequence in the input sequence
arr[]. The elements not included in the maximal increasing sequence should be removed in order the array to become sorted.Solution:
Link
23. Write a program, which reads the integer numbers
N and K from the console and prints all variations of K elements of the numbers in the interval [1…N].Example: N = 3 à {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}
Guidelines: Start from the first variation in the lexicographical order: {1, 1, …} K times. Think of this as k-digit number. To obtain the next variation, increase the last digit. If it becomes greater than N, change it to 1 and increase the next digit on the left. Do the same on the left until the first digit goes greater than N.
Solution:
Link
← Back