Programming Taskbook

 E-mail: Password:

Russian 1100 training tasks on programming

©  M. E. Abramyan (Southern Federal University), 1998–2021

 Main Tasks Examples PT for MPI-2

 Overview Input-output operations Task groups Begin Integer Boolean If Case For While Series Proc Func Minmax Array Matrix String File Text Param Recur Dynamic Dynamic (obj) Tree Tree (obj)
 Tasks | Task groups | Param

# Structured data types in procedures and functions

All tasks of this section require to write a procedure or function and then use it for input data processing. Parameters of any function are assumed to be an input ones; if the kind of a procedure parameter is not specified explicitly then this parameter is assumed to be an input one too.

## Procedures and functions: arrays processing

Any given array should be input in the following order: its size (one integer for one-dimensional arrays, two integers for matrices, that is, two-dimensional arrays) and then all its elements in ascending order of indices (the elements of matrices should be input by rows).

The size of any one-dimensional array as well as the amount of rows and columns of any matrix are assumed to be in the range 1 to 10 if the task does not specify them explicitly. The order number of the first element of one-dimensional array is assumed to be equal to 1; the order number of the first row (column) of matrix is assumed to be equal to 1 too.

Procedures and functions that perform array processing should use no additional array of the same size.

Param1°. Write an integer function MinElem(AN) that returns the value of the minimal element of an array A of N integers. Using this function, find the minimal elements of three given arrays A, BC whose sizes are NA, NBNC respectively.

Param2. Write an integer function MaxNum(AN) that returns the order number of the maximal element of an array A of N real numbers. Using this function, find the order numbers of the maximal elements of three given arrays A, BC whose sizes are NA, NBNC respectively.

Param3. Write a procedure MinmaxNum(ANNMinNMax) that finds the order numbers NMin and NMax of the minimal and the maximal element of an array A of N real numbers (integers NMin and NMax are output parameters). Using this procedure, find the order numbers of the minimal and the maximal elements of three given arrays A, BC whose sizes are NA, NBNC respectively.

Param4. Write a procedure Inv(AN) that changes the order of elements of an array A of N real numbers to inverse one (the array A is an input and output parameter). Using this procedure, change order of elements of arrays A, BC whose sizes are NA, NBNC respectively.

Param5. Write a procedure Smooth1(AN) that performs smoothing an array A of N real numbers as follows: each element AK is replaced with the average of initial values of K first elements of the given array A. The array A is an input and output parameter. Using five calls of this procedure, perform smoothing a given array A of N real numbers five times successively; output array elements after each smoothing.

Param6. Write a procedure Smooth2(AN) that performs smoothing an array A of N real numbers as follows: an element A1 remains unchanged; elements AK (K = 2, …, N) is replaced with the average of initial values of elements AK−1 and AK. The array A is an input and output parameter. Using five calls of this procedure, perform smoothing a given array A of N real numbers five times successively; output array elements after each smoothing.

Param7. Write a procedure Smooth3(AN) that performs smoothing an array A of N real numbers as follows: each array element is replaced with the average of initial values of this element and its neighbors. The array A is an input and output parameter. Using five calls of this procedure, perform smoothing a given array A of N real numbers five times successively; output array elements after each smoothing.

Param8. Write a procedure RemoveX(ANX) that removes all elements equal an integer X from an array A of N integers. The array A and its size N are input and output parameters. Using this procedure, remove elements with given values XA, XBXC from three given arrays A, BC of size NA, NBNC respectively and output the new size and elements of each changed array.

Param9. Write a procedure RemoveForInc(AN) that removes some elements from an array A of N real numbers so that the values of elements being remained were in ascending order: the first element remains unchanged, the second element must be removed if its value is less than the value of the first one, the third element must be removed if its value is less than the value of the previous element being remained, and so on. For instance, the array of elements 5.5, 2.5, 4.6, 7.2, 5.8, 9.4 must be changed to 5.5, 7.2, 9.4. All procedure parameters are input and output ones. Using this procedure, change three given arrays A, BC whose sizes are NA, NBNC respectively and output the new size and elements of each changed array.

Param10. Write a procedure DoubleX(ANX) that doubles occurrences of all elements equal an integer X for an array A of N integers. The array A and its size N are input and output parameters. Using this procedure, double occurrences of elements with given values XA, XBXC for three given arrays A, BC of size NA, NBNC respectively and output the new size and elements of each changed array.

Param11. Write a procedure SortArray(AN) that sorts an array A of N real numbers in ascending order. The array A is an input and output parameter. Using this procedure, sort three given arrays A, BC of size NA, NBNC respectively.

Param12. Write a procedure SortIndex(ANI) that creates an index array I for an array A of N real numbers. The index array contains order numbers of elements of array A so that they correspond to array elements in ascending order of their values (the array A remains unchanged). The index array I is an output parameter. Using this procedure, create index arrays for three given arrays A, BC of size NA, NBNC respectively.

Param13. Write a procedure Hill(AN) that changes order of elements of an array A of N real numbers as follows: the minimal element of the array must be the first one, an element, whose value is the next to minimal value, must be the last one, an element with the next value must be the second one, and so on (as a result, the diagram of values of the array elements will be similar to a hill). The array A is an input and output parameter. Using this procedure, change three given arrays A, BC of size NA, NBNC respectively.

Param14. Write a procedure Split1(ANABNBCNC) that copies elements of an array A of NA real numbers to arrays B and C so that the array B contains all elements of the array A with odd order numbers (1, 3, …) and the array C contains all elements of the array A with even order numbers (2, 4, …). The arrays B, C and their sizes NB, NC are output parameters. Apply this procedure to a given array A of size NA and output the size and the elements for each of the resulting arrays B and C.

Param15. Write a procedure Split2(ANABNBCNC) that copies elements of an array A of NA integers to arrays B and C so that the array B contains all elements whose values are even numbers and the array C contains all elements whose values are odd numbers (in the same order). The arrays B, C and their sizes NB, NC are output parameters. Apply this procedure to a given array A of size NA and output the size and the elements for each of the resulting arrays B and C.

Param16. Write a procedure ArrayToMatrRow(AKMNB) that copies elements of an array A of K real numbers to an M × N matrix B (by rows). "Superfluous" array elements must be ignored; if the size of the array is less than the amount of matrix elements then zero value must be assigned to remaining matrix elements. Two-dimensional array B is an output parameter. Having input an array A of size K, integers M, N and using this procedure, create a matrix B and output its elements.

Param17°. Write a procedure ArrayToMatrCol(AKMNB) that copies elements of an array A of K real numbers to an M × N matrix B (by columns). "Superfluous" array elements must be ignored; if the size of the array is less than the amount of matrix elements then zero value must be assigned to remaining matrix elements. Two-dimensional array B is an output parameter. Having input an array A of size K, integers M, N and using this procedure, create a matrix B and output its elements.

Param18. Write a procedure Chessboard(MNA) that creates an M × N matrix A whose elements are integers 0 and 1, which are arranged in "chessboard" order, and A1,1 = 0. Two-dimensional array A is an output parameter. Having input integers M, N and using this procedure, create an M × N matrix A.

Param19. Write a real-valued function Norm1(AMN) that computes the norm of an M × N matrix A of real numbers using the formula

Norm1(AMN) = max {|A1,J| + |A2,J| + … + |AM,J|},

where the maximum is being found over J = 1, …, N. Having input an M × N matrix A, output Norm1(AKN), K = 1, …, M.

Param20. Write a real-valued function Norm2(AMN) that computes the norm of an M × N matrix A of real numbers using the formula

Norm2(AMN) = max {|AI,1| + |AI,2| + … + |AI,N|},

where the maximum is being found over I = 1, …, M. Having input an M × N matrix A, output Norm2(AKN), K = 1, …, M.

Param21. Write a real-valued function SumRow(AMNK) that returns the sum of elements in K-th row of an M × N matrix A of real numbers (if K is out of the range 1 to M then the function returns 0). Output the return value of SumRow(AMNK) for a given M × N matrix A and three given integers K.

Param22. Write a real-valued function SumCol(AMNK) that returns the sum of elements in K-th column of an M × N matrix A of real numbers (if K is out of the range 1 to N then the function returns 0). Output the return value of SumCol(AMNK) for a given M × N matrix A and three given integers K.

Param23. Write a procedure SwapRow(AMNK1K2) that exchanges K1-th and K2-th row of an M × N matrix A of real numbers. The matrix A is an input and output parameter; if K1 or K2 are out of the range 1 to M then the matrix remains unchanged. Having input an M × N matrix A and two integers K1, K2 and using this procedure, exchange K1-th and K2-th row of the matrix A.

Param24. Write a procedure SwapCol(AMNK1K2) that exchanges K1-th and K2-th column of an M × N matrix A of real numbers. The matrix A is an input and output parameter; if K1 or K2 are out of the range 1 to N then the matrix remains unchanged. Having input an M × N matrix A and two integers K1, K2 and using this procedure, exchange K1-th and K2-th column of the matrix A.

Param25. Write a procedure Transp(AM) that transposes a real-valued square matrix A of order M (that is, reflects its elements about the main diagonal). The matrix A is an input and output parameter. Using this procedure, transpose the given matrix A of order M.

Param26. Write a procedure RemoveRows(AMNK1K2) that removes rows with the order numbers in the range K1 to K2 from an M × N matrix A of real numbers (integers K1 and K2 are assumed to satisfy the double inequality 1 < K1 ≤ K2). If K1 > M then the matrix remains unchanged, if K2 > M then rows with numbers from K1 to M must be removed. Two-dimensional array A and integers M, N are input and output parameters. Having input an M × N matrix A and two integers K1, K2 and using this procedure, remove rows with the order numbers in the range K1 to K2 from the given matrix and output a new order and elements of the resulting matrix.

Param27. Write a procedure RemoveCols(AMNK1K2) that removes columns with the order numbers in the range K1 to K2 from an M × N matrix A of real numbers (integers K1 and K2 are assumed to satisfy the double inequality 1 < K1 ≤ K2). If K1 > N then the matrix remains unchanged, if K2 > N then rows with numbers from K1 to N must be removed. Two-dimensional array A and integers M, N are input and output parameters. Having input an M × N matrix A and two integers K1, K2 and using this procedure, remove columns with the order numbers in the range K1 to K2 from the given matrix and output a new order and elements of the resulting matrix.

Param28. Write a procedure RemoveRowCol(AMNKL) that removes K-th row and L-th column simultaneously from an M × N matrix A of real numbers (integers K and L are assumed to satisfy the inequalities M > 1, N > 1). If K > M or L > N then the matrix remains unchanged. Two-dimensional array A and integers M, N are input and output parameters. Having input an M × N matrix A and two integers K, L, apply this procedure to the given matrix and output a new order and elements of the resulting matrix.

Param29. Write a procedure SortCols(AMN) that rearrange columns of an M × N matrix A of integers in ascending lexicographic order (that is, for comparison of two columns their first distinct elements with the equal order numbers must be compared). Two-dimensional array A is an input and output parameter. Using this procedure, sort columns of a given M × N matrix A.

## Procedures and functions: strings processing

Param30°. Write an integer function IsIdent(S) that indicates whether a string S is a valid identifier, that is, a nonempty string that does not begin with a digit and contains Latin letters, digits, and a character "_" only. If S is a valid identifier then the function returns 0. If S is an empty string or begins with a digit then the function returns −1 or −2 respectively. If S contains invalid characters then the function returns the order number of the first invalid character. Using this function, check five given strings.

Param31. Write a string function FillStr(SN) that returns a string of length N containing repeating copies of the template string S (the last copy of S may be contained partially in the resulting string). Having input an integer N and five template strings and using this function, create five resulting strings of length N.

Param32. Write a procedure UpCaseLat(S) that converts all Latin small letters of a string S to uppercase (others characters of S must remain unchanged). A string S is an input and output parameter. Using this procedure, process five given strings.

Param33. Write a procedure LowCaseLat(S) that converts all Latin capital letters of a string S to lowercase (others characters of S must remain unchanged). A string S is an input and output parameter. Using this procedure, process five given strings.

Param34. Write a procedure TrimLeftC(SC) that removes all leading characters equal a character C from a string S. A string S is an input and output parameter. Having input a character C and five strings and using this procedure, process the given strings.

Param35. Write a procedure TrimRightC(SC) that removes all trailing characters equal a character C from a string S. A string S is an input and output parameter. Having input a character C and five strings and using this procedure, process the given strings.

Param36. Write a string function InvStr(SKN) that returns an inverted substring of a string S. The substring contains N characters of S (starting at a character with the order number K) in inverse order. If K is greater than the length of S then the function returns an empty string; if the length of S is less than K + N then all characters of S starting at its K-th character must be inverted. Output return values of this function for a given string S and each of three pairs of positive integers (K1N1), (K2N2), (K3N3).

Param37. Write an integer function PosSub(S0SKN) that searches for the first occurrence of a string S0 within a substring of a string S (the substring contains N characters of S starting at a character with the order number K). The function returns the order number of the first character of this occurrence within S. If K is greater than the length of S then the function returns 0; if the length of S is less than K + N then all characters of S starting at its K-th character must be analyzed. If the required substring of S does not contain occurrences of S0 then the function returns 0. Output return values of this function for given strings S0, S and each of three pairs of positive integers (K1N1), (K2N2), (K3N3).

Param38. Write an integer function PosLast(S0S) that searches for the last occurrence of a string S0 within a string S and returns the order number of the first character of this occurrence. If the string S does not contain occurrences of S0 then the function returns 0. Output return values of this function for five given pairs of strings (S0, S).

Param39. Write an integer function PosK(S0SK) that searches for K-th occurrence (K > 0) of a string S0 within a string S and returns the order number of the first character of this occurrence. The string S is assumed to contain no overlapping occurrences of the substring S0. If the string S does not contain occurrences of S0 then the function returns 0. Output return values of this function for five given triples (S0, SK).

Param40°. Write a string function WordK(SK) that returns K-th word of a string S (a word is defined as a character sequence that does not contain blank characters and is bounded by blank characters or the string beginning/end). If the amount of words in the string S is less than K then the function returns an empty string. Having input a string S and three positive integers K1, K2K3 and using this function, extract words with the given order numbers from the given string.

Param41. Write a procedure SplitStr(SWN) that creates an array W of all words being contained in a string S. The array W of strings and its size N are output parameters. A word is defined as a character sequence that does not contain blank characters and is bounded by blank characters or the string beginning/end; the string S is assumed to contain no more than 10 words. Using this function, output the amount N of words in the given string S and also all these words.

Param42. Write a string function CompressStr(S) that compresses a string S and returns the compressed string. The string compression must be carried out as follows: each substring consisting of 4 or more equal characters C is replaced by the string "C{K}", where K is the amount of characters C (the string being compressed is assumed to contain no braces "{}"). For example, the string "bbbccccce" must be compressed to "bbbc{5}e". Using this function, compress five given strings.

Param43. Write a string function DecompressStr(S) that restores a string, which was compressed by a function CompressStr (see Param42). An input parameter S is a compressed string; the function returns the decompressed value of the string S. Using this function, restore five given compressed strings.

Param44. Write a string function DecToBin(N) that returns a string containing the binary representation of a nonnegative integer N. The string consists of characters "0", "1" and does not contain leading zeros (except for the representation of zero number). Using this function, output binary representations of five given integers.

Param45. Write a string function DecToHex(N) that returns a string containing the hexadecimal representation of a nonnegative integer N. The string consists of characters "0"–"9", "A"–"F" and does not contain leading zeros (except for the representation of zero number). Using this function, output hexadecimal representations of five given integers.

Param46. Write an integer function BinToDec(S) that returns a nonnegative integer whose binary representation is contained in a string parameter S. The parameter S consists of characters "0", "1" and does not contain leading zeros (except for the representation of zero number). Using this function, output five integers whose binary representations are given.

Param47. Write an integer function HexToDec(S) that returns a nonnegative integer whose hexadecimal representation is contained in a string parameter S. The parameter S consists of characters "0"–"9", "A"–"F" and does not contain leading zeros (except for the representation of zero number). Using this function, output five integers whose hexadecimal representations are given.

## Procedures and functions: files processing

Param48. Write an integer function IntFileSize(S) that returns the amount of components in a binary file of integers called S. If the required file does not exist then the function returns −1. Using this function, output the amount of components for three binary files of integers with given names.

Param49°. Write an integer function LineCount(S) that returns the amount of lines in a text file called S. If the required file does not exist then the function returns −1. Using this function, output the amount of lines for three text files with given names.

Param50. Write a procedure InvIntFile(S) that changes the order of components of a binary file of integers called S to inverse one. If the required file does not exist then the procedure performs no actions. Using this procedure, process three binary files of integers with given names.

Param51. Write a procedure AddLineNumbers(SNKL) that adds the number of each line of a text file called S to the beginning of this line; the first line receives the number N, the second line receives the number N + 1, and so on. Any number is right-aligned within K first character positions of a line and is separated from the following text by L blank characters (K > 0, L > 0). If a line is empty then its number should not contain trailing blank characters. Apply this procedure to a given text file using given values of parameters N, KL.

Param52. Write a procedure RemoveLineNumbers(S) that removes order numbers (with leading and trailing blank characters) from the beginning of each line of a text file called S (the format of order numbers is described in Param51). If file lines do not contain order numbers then the procedure performs no actions. Apply this procedure to a given text file.

Param53°. Write a procedure SplitIntFile(S0KS1S2) that copies first K (≥ 0) components of an existing file called S0 to a new file called S1 and other components of this file to a new file called S2. All files are assumed to be binary files of integers; one of the resulting files may be empty. Apply this procedure to a given file called S0 using given values of K, S1S2.

Param54. Write a procedure SplitText(S0KS1S2) that copies first K (≥ 0) lines of an existing text file called S0 to a new text file called S1 and other lines of this file to a new text file called S2 (one of the resulting files may be empty). Apply this procedure to a given file called S0 using given values of K, S1 S2.

Param55. Write a procedure StringFileToText(S) that converts a binary file of strings called S to a new text file with the same name. Using this procedure, convert two given files of strings with the names S1, S2 to text files.

Param56. Write a procedure TextToStringFile(S) that converts a text file called S to a new binary file of strings with the same name. Using this procedure, convert two given text files with the names S1, S2 to binary files of strings.

Param57. Write a procedure EncodeText(SK) that encrypts the contents of a text file called S using the right cyclic shift of any Latin letter by K positions of the English alphabet (0 < K < 10). For instance, if K = 3 then the letter "A" is encoded by the letter "D", "a" is encoded by "d", "B" is encoded by "E", "z" is encoded by "c", and so on. Blank characters and punctuation marks should not be changed. Having input an integer K and using this procedure, encrypt a text file with the given name.

Param58. Write a procedure DecodeText(SK) that decrypts the contents of a text file called S provided that this file was encrypted by the method described in Param57 with using an integer parameter K. Having input an integer K and using this procedure, decrypt a text file with the given name.

## Procedures and functions: records processing

Fields of each date record should be input/output in the following order: Day, Month, Year. Fields of each 2D-point record should be input/output in the following order: X (an x-coordinate), Y (an y-coordinate).

Param59°. Define a new type called TDate that is a record with three integer fields: Day (a day number), Month (a month number), Year (a year number). Also write a logical function LeapYear(D) with a parameter D of TDate type. The function returns True if a year of date D is a leap year, and False otherwise. Output the return values of this function for five given dates (all dates are assumed to be correct). Note that a year is a leap year if it is divisible by 4 except for years that are divisible by 100 and are not divisible by 400.

Param60°. Using the TDate type and the LeapYear function (see Param59), write an integer function DaysInMonth(D) with a parameter D of TDate type. The function returns the amount of days for the month of date D. Output the return values of this function for five given dates (all dates are assumed to be correct).

Param61°. Using the TDate type and the DaysInMonth function (see Param59 and Param60), write an integer function CheckDate(D) with a parameter D of TDate type. If the date D is a correct date then the function returns 0; if the date D contains an invalid month number or invalid day number for the correct month then the function returns 1 or 2 respectively. Output the return values of this function for five given dates.

Param62. Using the TDate type and the DaysInMonth and CheckDate functions (see Param59−Param61), write a procedure PrevDate(D) that changes a correct date D (of TDate type) to the previous one; if D contains an invalid date then it remains unchanged. The parameter D is an input and output parameter. Apply this procedure to five given dates.

Param63. Using the TDate type and the DaysInMonth and CheckDate functions (see Param59−Param61), write a procedure NextDate(D) that changes a correct date D (of TDate type) to the next one; if D contains an invalid date then it remains unchanged. The parameter D is an input and output parameter. Apply this procedure to five given dates.

Param64. Define a new type called TPoint that is a record with two real-valued fields: X (an x-coordinate), Y (an y-coordinate). Also write a real-valued function Leng(AB) that returns the length of a segment AB (A and B are input parameters of TPoint type):

|AB| = ((A.X − B.X)2 + (A.Y − B.Y)2)1/2.

Using this function, output lengths of segments AB, AC, AD provided that the coordinates of points AB, CD are given.

Param65. Using the TPoint type and the Leng function (see Param64), define a new type called TTriangle that is a record with three fields A, BC (triangle vertices) of TPoint type, and write a real-valued function Perim(T) that returns the perimeter of a triangle T (T is an input parameter of TTriangle type). Using this function, find perimeters of triangles ABC, ABD, ACD provided that the coordinates of points AB, CD are given.

Param66. Using the TPoint and TTriangle types and the Leng and Perim functions (see Param64 and Param65), write a real-valued function Area(T) that returns the area of a triangle T (T is an input parameter of TTriangle type):

SABC = (p·(p − |AB|)·(p − |AC|)·(p − |BC|))1/2,

where p is the half-perimeter. Using this function, find the areas of triangles ABC, ABD, ACD provided that the coordinates of points AB, CD are given.

Param67. Using the TPoint and TTriangle types and the Leng and Area functions (see Param64–Param66), write a real-valued function Dist(PAB) that returns the distance D(PAB) between a point P and a line AB:

D(PAB) = 2·SPAB/|AB|,

where SPAB is the area of the triangle PAB (parameters P, AB are input parameters of TPoint type). Using this function, find the distance between a point P and each of lines AB, ACBC provided that the coordinates of points PA, BC are given.

Param68. Using the TPoint and TTriangle types and the Dist function (see Param64, Param65, Param67), write a procedure Alts(Th1h2h3) that evaluates the altitudes h1, h2h3 drawn from the vertices T.A, T.B, T.C of a triangle T (T is an input parameter of TTriangle type, h1, h2, h3 are output real-valued parameters). Using this procedure, evaluate the altitudes of each of triangles ABC, ABD, ACD provided that the coordinates of points AB, CD are given.

Param69. Using the TPoint type and the Leng function (see Param64), write a real-valued function PerimN(PN) that returns the perimeter of a polygon with N (> 2) vertices. The polygon vertices have the TPoint type; an array P contains all vertices in order of walk. Using this function, find the perimeters of three polygons provided that the amount of vertices and the coordinates of all vertices are given for each polygon.

Param70. Using the TPoint and TTriangle types and the Area function (see Param64–Param66), write a real-valued function AreaN(PN) that returns the area of a convex polygon with N (> 2) vertices. The polygon vertices have the TPoint type; an array P contains all vertices in order of walk. Using this function, find the areas of three polygons provided that the amount of vertices and the coordinates of all vertices are given for each polygon. Designed byM. E. Abramyan and V. N. Braguilevsky Last revised:01.01.2021