Увод в програмирането, Информатика 2013/14

Първото домашно се състои от 10 задачи за самостоятелна работа от Сборник от задачи по програмиране на C++ на М. Тодорова, П. Армянов, Д. Петкова, К. Георгиев. Всяка правилно решено задача носи 2 т.

Моля, изпращайте решенията си като ZIP файл, който съдържа по един .cpp файл за всяка задача. Решението на всяка задача трябва да бъде във файл с име progX.cpp (с малки латински букви), където 1 <= X <= 10 е номерът на съответната задача.

По-долу са дадени условията на задачите, както и страница и номер в сборника.

Внимание: всички задачи ще бъдат тествани автоматично, затова е важно извеждането на екрана да спазва абсолютно точно това, което е указано в задачата! На лекции ще получите повече информация.

Внимание: всички задачи ще бъдат проверени автоматично за преписване. Файловете с голямо съвпадение ще бъдат проверени ръчно от лектора и при установено взаимстване ще бъдат анулирани.

Задача 1 (стр. 185 / зад. 39). Дадени са n триъгълника (1 ≤ n ≤ 20) с дължини на страните a_i, b_i и c_i (0 ≤ i ≤ n - 1). Да се напише програма, която намира номера на триъгълника с най-голямо лице. Вход: числото n, нов ред, след което n реда, като на всеки ред има три дробни числа, разделени с интервал и задаващи страните на поредния триъгълник. Изход: цяло число i (0 ≤ i ≤ n - 1), означаващо поредния номер на триъгълника с най-голямо лице.

Задача 2 (стр. 185 / зад. 43). Два реда на една матрица си приличат, ако съвпадат множествата от числата, съставящи редовете. Да се напише програма, която намира номерата на всички редове на матрица от цели числа A с размерност n x m (1 ≤ n ≤ 20 и 1 ≤ m ≤ 30), които приличат на зададен чрез поредния си номер k (0 ≤ k ≤ n - 1) на А. Вход: числото n, интервал, числото m, интервал, числото k, нов ред, m реда с по n цели числа на всеки, отделени с интервал. Изход: Номерата на всички редове, които си приличат с k-тия ред, подредени във възходящ ред и разделени с интервал. Номерът на самия k-ти ред да не се извежда.

Задача 3 (стр. 186 / зад. 56). Квадратна матрица A с размерност n (1 ≤ n ≤ 20) е триъгълна, ако за елементите ѝ е в сила: a_i,j = 0, ако i > j и a_i,j ≠ 0, ако i ≤ j или a_i,j = 0, ако i < j и a_i,j ≠ 0, ако j ≤ i, за 0 ≤ i,j ≤ n - 1). Да се напише програма, която определя дали дадена матрица A е триъгълна. Вход: числото n, нов ред, n реда с по n цели числа на всеки, отделени с интервал. Изход: числото 1, ако A е триъгълна, числото 0 в противен случай.

Задача 4 (стр. 187 / зад. 62). Дадена е квадратна таблица A с размерност n x n (1 ≤ n ≤ 20) от низове, съдържащи думи с максимална дължина 9. Да се напише програма, която намира изречението, получено след обхождане на A по спирала в посока обратна на движението на часовниковата стрелка, започвайки от долния десен ъгъл. Вход: числото n, нов ред, n² реда с по един низ ред, описващи елементите на матрицата по редове (т.е. по реда (0, 0), (0, 1), ... (0, n - 1), (1, 0), (1, 1), .... (1, n - 1), ... (n - 1, 0), (n - 1, 1), ... (n - 1, n - 1)). Изход: Точно един ред с полученото изречение, в което думите са разделени с по един интервал.

Задача 5 (стр. 296 / зад. 20). Да се дефинира функция char const* reverseWordsOnly(const char*), която получава като параметър символен низ и връща символен низ, получен от дадения, но отделните думи (и само те) са обърнати. Думите са произволни редици от символи. За разделители служат ‘ ‘, ‘, ‘, ‘;’ и ‘.’. Да се напише програма, която въвежда низ до 1000 символа от клавиатурата и извежда получения резултат от функцията reverseWordsOnly на екрана. Вход: Входният низ, записан на един ред. Изход: Резултатът от функцията, записан на един ред.

Задача 6 (стр. 297 / зад. 31). Нека alpha е редица от 26 знака. Да се дефинира функция char* encode(char* source, char const* alpha), която заменя всяка малка латинска буква в символния низ source със съответен символ от символния низ alpha. Съответствието е следното: ‘a’ се заменя alpha[0], ‘b’ се заменя с alpha[1], … ,’y’ се заменя с alpha[24], ‘z’ се заменя с alpha[25]. Останалите символи не се променят. Да се напише програма, която въвежда низ source до 1000 символа от клавиатурата и низ alpha и извежда получения резултат от функцията encode на екрана. Вход: Низът source, нов ред, низът alpha. Изход: Резултатът от функцията, записан на един ред.

Задача 7 (стр. 298 / зад. 37). Да се напише програма, която за дадена числова редица a₀, a₁, ..., a_n-1 (1 ≤ n ≤ 20) намира дължината на най-дългата ѝ ненамаляваща подредица a_i1, a_i2, ..., a_ik (a_i1 ≤ a_i2 ≤ ... ≤ a_ik), където i₁ < i₂ < … < i_k. Вход: числото n, нов ред, целите числа от a₀ до a_n-1, разделени със интервали. Изход: Дължината на най-дългата ненамаляваща подредица като цяло число.

Задача 8 (стр. 351 / зад. 5). Да се дефинира рекурсивна функция, която променя дадено естествено число n < 1000000000 като заменя, всяко срещане на дадена десетична цифра a в него с друга десетична цифра b. Вход: числото n, нов ред, цифрите a и b, разделени с интервал. Изход: числото n след замяната на всяка цифра a с b.

Задача 9 (стр. 351 / зад. 8). Да се дефинира рекурсивна функция, която по дадени цяло число x и цяло число n ≥ 2, намира стойността на израза ( ...(((x + 2)x + 3)x + 4)x + ...  + n - 1)x + n. Вход: числото n, нов ред, числото x. Изход: стойността на израза.

Задача 10 (стр. 354 / зад. 40). Да се напише програма, която генерира всички разбивания на дадено естествено число n (n > 1) на събираеми i₁, i₂, ..., i_k, които са естествени числа и за които i₁ ≤ i₂ ≤ ... ≤ i_m и i₁ + i₂ + ... + i_k = n. Казваме, че едно разбиване i₁, i₂, ..., i_k предхожда друго разбиване j₁, j₂, ..., j_l , ако i₁ = j₁, i₂ = j₂, ... i_m-1 = j_m-1, но i_m < j_m за някое m ( 1 ≤ m ≤ min(k,l)). Вход: числото n. Изход: всички възможни разбивания на n, без повторения, като събираемите на всяко разбиване са записани като ненамаляваща редица и са разделени с интервали. Разбиванията да са подредени по "предхождане".