Страница на курса "Програмиране 101"
Зимен семестър, 2011г.

HomeLectionsProblemsScores

 

Важно: страницата е преместена ето тук. Тази страница е запазена единствено като архив. Ползвайте новата страница за последна версия на проблемите (с корекции в условията и решенията), по-четим фонт, а също така и много нови задачи!

Задачи

Disclaimer: Copy-pase-ът вкара някакви шпации на произволни места, уби super- и subscript-ите, а също така и обърка част от пълните и непълните членове (wasntme).

  1. Сливащи се свързани списъци
  2. Рандом генератор чрез монета
  3. Задачата „Нагоре, надолу”
  4. Задача за разделянето на тортата
  5. Подинтервал с максимална сума
  6. Има ли цикъл?
  7. Blind Guardians
  8. Тройка с нулева сума
  9. Повтарящ се елемент в масив
  10. Неповтарящ се елемент в масив, v1.0
  11. Неповтарящ се елемент в масив, v2.0
  12. Задача за трите мравки
  13. Фалшиви хапчета
  14. Задача за 12-те монети
  15. Сложно уравнение
  16. Точна степен на две
  17. Lowest bit
  18. Нула или едно
  19. Бързо умножение по седем
  20. Random Shuffle
  21. Разбъркване на тесте карти
  22. Japanese Riddle
  23. Странна редица
  24. Битови подмаски
  25. Бързо вдигане на степен
  26. Точно едно повтарящо се число
  27. Точно едно липсващо число
  28. Омагьосани предмети
  29. Game 21
  30. Първо липсващо естествено число
  31. Липсващо число в сортиран масив
  32. Cast
  33. Statement vs. Block
  34. Method vs. Function
  35. Logical vs. Binary operators
  36. Unique
  37. Задачата с крушките
  38. Задачата с прасетата и отровата
  39. Най-големи числа с поне 2 повторения
  40. Структура данни за медиана
  41. Произведения на всички числа без едно в масив
  42. Въпрос за Живота, Вселената и Всичко Останало
  43. Разделяне на Тортата на 8 Парчета
  44. Ъгъл Между Стрелките на Часовник
  45. Всички Пермутации на String
  46. Игра на Кръгла Маса
  47. Triminoes
  48. Избор на Град Според Популацията Му
  49. Appointment Problem
  50. Произволен Елемент от Генератор
  51. Стъпала
  52. Петата Карта

 

1. Сливащи се свързани списъци

Дадени са ни указатели към първите елементи на два ациклични едносвързани списъка. Можете ли с константна памет и линейно време да определите дали в някой елемент единият списък не се "слива" във втория (тоест двата да завършват в един и същ елемент). Ако да, можете ли да намерите кой е първият им общ елемент? Опишете алгоритъма си.

 

2. Рандом генератор чрез монета

Имайки на разположение генератор на случайни булеви величини (true, false), напишете функция, която генерира случайни числа в интервала [0, 1].
Докажете, че генерираните от нея числа са равномерно разпределени.

 

3. Задачата „Нагоре, надолу” (от шоуто на Къци)

По случаен начин е избрано цяло число num между 1 и 1000. Имате функция guess(x), която връща 0, ако num == x, -1 ако x < num, и +1 ако x > num. Изградете алгоритъм, който, познава числото num с минимален брой викания на функцията guess(x). Определете броя извиквания при най-лошия избор на num за вашия алгоритъм.

 

4. Задача за разделянето на тортата

Даден е бял правоъгълник, във вътрешността на който е нарисуван друг, черен правоъгълник, чиито страни може да не са успоредни на тези на белия. Може ли с една единствена права линия да се раздели остатъка от белия правоъгълник на части с равна площ?

 

5. Подинтервал с максимална сума

Даден е масив с N числа. Изградете алгоритъм, който намира негов подинтервал с максимална сума. Подинтервал е поредица от последователни негови елементи.

 

6. Има ли цикъл?

Даден е указател към първия елемент на (потенциално много много дълъг) едносвързан списък, чиито брой елементи не знаем. Възможно е той да се зацикля (тоест връзката на някой от елементите му да сочи към предходен такъв). Можете ли да измислите начин за проверка с константна памет и линейно време дали списъкът се зацикля или не? Нямаме право да променяме елементите на списъка по какъвто и да било начин.

 

7. Blind Guardians

Ели се намира в стая, която има 2 врати: едната води към нейните най-големи кошмари (място, където ноктите й се чупят по-често, косата й не е толкова блестяща, не всички я харесват, и всеки ден има изпити по анализ), а другата - към нейния рай (всъщност не сме много сигурни какво е това, но бихме могли да предположим, че Станчо се намира там). Всяка от вратите се охранява от пазач, единият от които винаги казва истината, а другият - винаги казва лъжата. Ели има право на един единствен въпрос и след това трябва да избере врата, през която да мине. Какъв би могъл да бъде този въпрос?

 

8. Тройка с нулева сума

Даден ви е масив с N цели числа (всяко от тях положително, отрицателно или нула). Изградете алгоритъм, който намира дали съществува тройка негови числа със сума нула. Разгледайте решения със сложности O(N**3), O(N**2 * logN), O(N**2). Можете ли да модифицирате алгоритъма си така, че да брои колко различни такива тройки има?

 

9. Повтарящ се елемент в масив

Даден е масив с N цели числа, като всяко от тях е между 1 и N, включително. Измислите алгоритъм, който проверява дали има повтарящо се число. Имате право да променяте елементите на масива. Каква най-добра сложност по време и по памет можете да направите?

 

10. Неповтарящ се елемент в масив, v1.0

Даден е масив с N (нечетен брой) цели числа. Всяко число се среща по два пъти с изключение на едно, което е уникално. Намерете това число.

 

11. Неповтарящ се елемент в масив, v2.0

Даден е масив с N (четен брой) цели числа. Всяко число се среща по два пъти с изключение на две, които са уникални и различни помежду си. Намерете тези числа.

 

12. Задача за трите мравки

В триъгълен съд има три мравки - всяка в един от ъглите на триъгълника. Едновременно всяка от тях тръгва към някой от другите ъгли. Какъв е шансът след като стигнат до ъгъла, към който са тръгнали, отново във всеки ъгъл да има точно по една мравка?

 

13. Фалшиви хапчета

Имате 10 буркана, пълни с хапчета. Казано ви е, че във всички буркани хапчетата тежат по 10 грама, с изключение на един, където хапчетата са по 9 грама. Разполагате с електронна везна, която прецизно измерва теглото на сложените върху нея обекти. Можете ли с едно единствено измерване на везната да определите в кой от бурканите хапчетата са по-леки?

 

14. Задача за 12-те монети

Дадени са ви 12 идентични монети, една от която е фалшива (тоест е направена от различен материал и съответно е по-лека или по-тежка). Дадена ви е и обикновена везна (на която от двете страни можете да сложите някакви обекти и тя ще ви покаже дали теглото им е равно, дали левите са по-леки или по-тежки). Можете ли с три измервания да определите коя е фалшивата монета и дали тя е по-лека или по-тежка?

 

15. Сложно уравнение

Дадено ви е, че A = 1, B = 2**A, C = 3**B, ..., Z = 26**Y, където операцията ** е вдигане на степен. Намерете (X - A) * (X - B) * (X - C) * ... * (X - Z) = ?.

 

16. Точна степен на две

Дадено ви е число N и от вас се иска да напишете възможно най-прост if() (с възможно най-малко операции в него), с който да проверите дали числото е точна степен на 2 или не. Не са разрешени цикли или по-сложни конструкции.
Примерна реализация би била if (!(N ^ 1) || !(N ^ 2) || !(N ^ 4) || !(N ^ 8) || ...), но тя е много по-дълга от оптималната, а също така зависи колко битов е типа на N.

 

17. Lowest bit

Дадено ви е положително цяло число N. Намерете неговия най-нисък ненулев бит (lowest bit) или по-точно числото, което представя той (ако индексът е 3, то върнете 2**3 = 8).
Примери: за числото 42 (101010) трябва да върнете 2, докато за 88 (1011000) трябва да върнете 8. Най-ниските битове са най-надясно в двоичния запис на числото.

 

18. Нула или едно

По дадено цяло число x съставете израз само от побитови операции и х и скоби, който се евалюира до true, ако числото е нула или едно, и до false ако е което и да е друго. Побитови операции са +, -, ~, |, &, ^, !, <<, >> приложени върху аргумента или константи.

 

19. Умножение по седем

Покажете начин за целочислено умножение по 7 използвайки само побитови операции. Побитови операции са +, -, ~, |, &, ^, !, << (shift left), >> (shift right).

 

20. Random Shuffle

Напишете алгоритъм, който разбърква по произволен начин елементите на дадено множество с N елемента. Покажете, че всяко разбъркване е възможно да се случи и докажете защо всеки от възможните изходи е с равен шанс (ако допуснете, че функцията rand() връща произволна стойност). Нямате право да ползвате вградената функция random_shuffle().

 

21. Разбъркване на тесте карти

Колко е очакваният брой разбърквания на стандартно тесте с карти (с 52 карти), които трябва да направите, преди да постигнете уникално подреждане (което никога до сега не се е срещало преди в историята на човечеството). Допускаме, че при разбъркване на картите получаваме с еднаква вероятност всяка възможна тяхна подредба.
Допълнителна информация: 100 милиарда хора, живяли някога на планетата.

 

22. Japanese Riddle

Дадени са ви:

  • 42 -> 1
  • 1337 -> 0
  • 669 -> 3
  • 1882 -> 4
  • 688 -> 5
  • 12345 -> 1
  • 67890 -> 5
  • 123 -> 0
  • 456 -> 2
  • 789 -> 3
Намерете 45678 -> ?

 

23. Странна редица

Дадена ви е редицата 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211. Намерете следващия й член.

 

24. Битови подмаски

Инфо:
За да записваме подмножества на някакво множество със сравнително малък брой елементи (до 32 или до 64) понякога е по-удобно (по-бързо и по-икономично откъм памет) вместо да записваме елементите в масив, да ги запазваме в едно единствено 32 (или 64) битово число. Ако i-тият елемент присъства в подмножеството, то числото ще има 1-ца на i-та позиция в двоичния си запис и обратно - ако не присъства ще има 0 на съответната позиция. Този метод се нарича ползване на битови маски (тъй като маската от битовете на числото определя кои елементи присъстват и кои не). Ето и пример за това. Да кажем в един учебен клас има 25 ученика. Учителят може да записва отсъстващите ученици в даден ден в един единствен int. Например 1050784, чието двоично записване е 100000000100010100000, би означавало, че 6, 8, 12 и 21-ви номер са отсъствали в дадения ден.
Понякога се налага да изброим (итерираме) всички подмножества на дадено множество. Подмножество на дадено множество е множеството от някои (потенциално всички или нито един) от елементите на първоначалното множеството.
Задача:
Напишете функция, която генерира всички непразни подмножества на дадено множество, зададено чрез битова маска. Тоест генерирайте всички негови ненулеви битови подмаски.

 

25. Бързо вдигане на степен

Напишете функция, която вдига число a на степен p. Има ли по-бързо от линейно решение?

 

26. Точно едно повтарящо се число

Дадени са ви N числа между 1 и N-1, включително. Точно едно от тях се повтаря. Намерете кое е то.

 

27. Точно едно липсващо число

Дадени са ви N-1 числа между 1 и N, включително, като точно едно от тях липсва (и няма повтарящи се). Намерете кое е то.

 

28. Омагьосани предмети

В редица са наредени N абсолютно еднакво-изглеждащи предмета, като един от тях е истински, а останалите са негови холограми. На всеки ход можем да пробваме да докоснем точно един от тях. Ако той е бил истинският, холограмите изчезват и ние печелим. Ако не е бил, то истинският разменя мястото си с холограмата от лявата му страна (ако има такава, тоест ако не е в най-лявата позиция) или с холограмата от дясната му страна (отново ако има такава). Измислете стратегия, с която със сигурност да уловите истинския предмет, независимо от това как той се е движил и къде се е намирал в началото.

 

29. Game 21

Играта 21 е известна игра, която се играе от двама души. В началото пред тях има купчинка с 21 монети. Играчите се редуват, започвайки от единия. Играчът, който е на ход, има право да махне 1, 2 или 3 монети от купчината (ако има толкова останали в нея). Играчът, който не може да направи ход (тоест не са останали монети) губи. Има ли стратегия, при която първият може да спечели, независимо от ходовете на втория? Опишете я.

 

30. Първо липсващо естествено число

Даден ви е масив с N естествени числа, които (потенциално) могат да бъдат много големи. Пита се кое е първото естествено число, което не фигурира в масива. За тази задача приемете, че естествените числа са целите, положителни числа.

 

31. Лиспващо число в сортиран масив

Даден ви е сортиран масив с N числа между 0 и N, включително, без повтарящи се числа, сортирани в нарастващ ред. Как бихте намерили лиспващото число?

 

32. Cast

За какво се използва термина "cast"? Защо се използва?

 

33. Statement vs. Block

Каква е разликата между statement и block?

 

34. Method vs. Function

Каква е разликата между метод и функция?

 

35. Logical vs. Binary operators

Каква е разликата между & и &&, както и между | и ||? Дайте пример, в който те не са взаимно-заменяеми.

 

36. Unique

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

 

37. Задачата с крушките

Намирате се в изолирана стая с три ключа за осветление - контролиращи три крушки в съседна стая, която не можете да видите. Как бихте могли да разберете кой ключ коя крушка контролира, ако веднъж отишли в стаята с крушките не можете да се върнете в стаята с ключовете?

 

38. Задачата с прасетата и отровата

Готвачът на краля приготви 1000 гозби за неговата сватба! Но кралските шпиони му съобщиха, че някой е сипал отрова в точно една от гозбите му. Отровата започва да се забелязва 2 часа след поемане на храната, а до сватбения пир остават... малко повече от два часа - тоест има време точно за една проба. За щастие, готвачът има на разположение много прасета, върху които може да експериментира - да им забърка смесица (от една или повече от гозбите) и да им я даде да я изядат. Така ако до два часа прасето умре, то в някоя от гозбите, които е изяло, е имало отрова. Колко най-малко прасета е нужно да са на разположение на готвача, за да може да определи в коя гозба е отровата в рамките на тези 2 часа? Примерно решение е да даде на 1000 прасета по точно една от гозбите, но има решение с много по-малко на брой. Тоест той гледа да минимизира не броя умрели прасета, а броя ползвани такива.

 

39. Най-големи числа с поне 2 повторения

Дадена ви е редица от числа. Намерете двете най-големи от тях, които се срещат поне 2 пъти.

 

40. Структура данни за медиана

Опишете структура данни, която поддържа бързо добавяне на число и бързо питане за медианата на досега добавените.

 

41. Произведения на всички числа без едно в масив

Имате масив с N числа и искате да върнете нов масив, в който на i-та позиция има произведението на всички числа с изключение на i-тото от първоначалния масив. Как бихте решили задачата, ако нямахте деление?

 

42. Въпросът за Живота, Вселената и Всичко Останало

Намерете отговора на Живота, Вселената и Всичко Останало.

 

43. Разделяне на Тортата на 8 Парчета

Дадена ви е кръгла торта. Как можете да я разделите на 8 еднакви парчета с 3 прави разреза?

 

44. Ъгъл Между Стрелките на Часовник

По даден час и минути определете какъв е (по-малкият) ъгъл между стрелките на аналогов часовник.

 

45. Всички Пермутации на String

Напишете функция, която печата всички пермутации на зададен string.

 

46. Игра на Кръгла Маса

Дадена е кръгла маса с радиус 10 сантиметра. Двама играчи се редуват и слагат по една монета с радиус 1 сантиметър на масата така, че да не застъпва никоя от досега сложените монети и да не пада от масата. Играчът, който не може да сложи момента губи. Има ли стратегия за първия играч, при която той винаги печели? Каква е тя?

 

47. Triminoes

Даден е квадрат със страна 2**N, разделен на малки квадратчета със страна 1. Едно от тях е оцветено в черно, всички останали в бяло. На всеки ход ние можем да поставим trimino, успоредно на страните на квадрата, ако то е разположено само върху бели плочки. Trimino е плочка от три квадратчета под формата на Г (тоест квадрат 2 на 2, на който липсва една от плочките). След поставянето му, трите бели плочки, върху които лежи стават черни. Възможно ли е да се оцвети целият квадрат в черно с поставяне на trimino-та? Как?

 

48. Избор на Град Според Популацията Му

Напишете функция, която по дадено множество от градове и тяхната популация, избира някой от тях, като шансът даден град да бъде избран е пропорционален на броя жители в него. Например ако градовете са София (1,263,328 жители), Стара Загора (150,081 жители), Варна (350,064 жители) би избрала София с шанс 71.638%, Стара Загора с шанс 8.511% и Варна с шанс 19.851%.

 

49. Appointment Problem

Зададено е множество от събития, зададени чрез тяхното начално време и крайно време. Изберете максимално (по брой) тяхно подмножество, така че никои две събития да не се застъпват (но може да се "докосват", тоест единото да почва точно когато свършва предходното).

 

50. Произволен Елемент от Генератор

Даден ви е (краен) генератор на числа (списък с неизвестен брой елементи, които НЕ можем да индексираме, единствено можем да искаме следващия елемент докато изчерпим всички). Измислете как с константна допълнителна памет и линейно (по броя генерирани елементи) време да изберете случаен елемент от него. Например ако генерираните елементи са били {3, 1, 5, 1, 5, 2, 7, 5}, То 2, 3 и 7 трябва да бъдат избрани с шанс 1/8, 1 да бъде избрано с шанс 1/4 и 5 да бъде избрано с шанс 3/8.

 

51. Стъпала

Човек изкачва стълбище с N стъпала. На всяка стъпка той или се качва на следващото стъпало, или изкачва две наведнъж (прескача едно). По колко различни начина може да изкачи стълбището? А ако броят на стъпалата е много голям (1,000,000,000)?

 

58. Петата Карта

От стандартно тесте карти с 52 карти биват изтеглени 5 произволни карти. Искаме да дадем 4 от тях на друг човек, така че по тях той да може да познае 5-тата. Каквъв "протокол" (стратегия) на комуникация биха могли да имат двамата човека за да определят еднозначно 5-тата карта по дадените 4? Картите се дават наредени (тоест ordered set), но не може да се подсказва по друг начин (като например някоя карта да е обърната или завъртяна).

 


Web design by Alexander 'espr1t' Georgiev, 2011