Вписване в сайта



комбинаторика

Четвъртък, 29 Декември 2011 07:15

комбинаторика

Написана от 
Оценете
(2 гласа)

Да се състави програма, чрез която се извеждат възможните комбинации на естествените числа от интервала от 1 до въведено от клавиатурата число N[4..10] и K[2..4] - за брой елементи в K-ти клас.
Пример: N=4, K=2 Изход: 1, 2; 1, 3; 1, 4; 2, 3; 2, 4; 3, 4 Брой комбинации 6
Решение (свободен достъп)

Да се състави програма (C++), чрез която се въвежда естествено число N от интервала [5..10].
Програма да изведе брой числа с различни цифри - всички N-цифрени числа, които нямат повтарящи се цифри и да съдържат само цифри от интервала [0..N-1]. Използвайте формула за изчисляване брой на пермутации.
Пример: N=10 Изход: 3265920
Решение

Иван решава парти да прави и си кани гости. Проблемът е, че на предното парти не беше особено весело и част от поканените се колебаят.
Иван, като един истински предвидлив организатор, иска да знае възможните комбинации от гости.
Да се състави програма (C++), чрез която се въвежда естествено число N [2..1002] и се извеждат всички възможни комбинации от подмножества с гости. Всяка отделна комбинация се отделя от останалите, с U се означава пореден номер на поканения.
Пример: 2 Изход: никой; U1; U2; U1,U2 - 4 комбинации
Решение

Съществува множество от N [3..12] елемента. Елементите в множеството са естествени числа.
Да се състави програма (C++), чрез която се въвежда N и се извеждат всички възможни разбивания, представяне на множеството като отделни подмножества. Отделните представяния не трябва да се повтарят и всяко отделно разбиване да съдържа всички начални елементи на множеството.
Пример: N=3 Изход: 5 броя: 1){1,2,3}; 2){1,2},{3}; 3) {1},{2},{3};4){1},{2,3}; 5){1,3},{2}
Решение

Една от хипотезите на Голдбах в областта на простите числа е:
Всяко четно число, по-голямо от 2, може да се представи като сума от две прости числа.
Да се състави програма, която илюстрира доказателство на твърдението от интервала [4..500].
Пример: 10 Изход: 3,7
Решение

Виноградов през 1937 година доказва, че всяко нечетно число, по-голямо от 7, може да се представи като сума на три нечетни прости.
Да се състави програма (C++), чрез която се въвежда естествено число N [101..10001].
Програмата да изведе всички комбинации от 2 и/ли 3 прости числа, чиято обща сума е равна на въведеното число.
Пример: N=19 Изход: 17+2; 11+7+1; 11+5+3; 13+5+1;
Решение

Да се състави програма, чрез която се въвеждат 3 едноцифрени числа, a,b,c [1..9].
Програмата да изведе най-малкото число N [10..999], което е кратно на 3 и има цифри измежду вече въведените числа.
Пример: a=2, b=3; c=4 Изход: 24
Решение

Да се състави програма, чрез която се въвеждат 3 естествени числа a,b,c [2..102] и се извежда число, формирано като сума или прозведение на a,b и е с минимална разлика от числото c.
Пример: a=8; b=10; c=65 Изход 64
Решение

Да се състави програма, която чрез функция с параметър естествено 4-цифрено число реализира играта крави и бикове.
Компютърът да генерира случайно естествено число като комбинация от 4 различни цифри, а потребителят да отгатва това число като въвежда свое 4-цифрено число.
Ако има съвпадение на дадена цифра в съответната позиция - това е 1 бик, ако има съвпадение на цифра, но в различна позиция - 1 крава.
Пример: компютър1234 и потребител 5217
Изход: 1 крава и 1 бик - 1 в случая е крава, а 2 е бик
Решение

Кипи напрегната конкуренция за заемане на по-голям пазарен дял.
Конструктивният отдел е изработил изделие, което ще изведе фирмата на по-добри пазарни позиции.
Заповедта на шефа е кратка и ясна: Всички машини да произвеждат само това изделие.
Всичко произведено директно се транспортира до пласментната мрежа.
Нужни са M детайла, имате N машини, всяка е с различна производителност. Програмата да извежда необходимото време за производство на всички детайли.
Пример: 100 детайла, 2 машини с производителност съответно 3 и 4 [s].
Изход: 171 секунди, машина 1 - 57; машина 2 - 42 и довършва следващия
Решение

Управителният съвет на един стадион обръща сериозно внимание относно повишената консумация на електроенергия след включване на новия електронен часовник.
Да се състави програма, чрез която се намира и извежда времето с най-висока и най-ниска консумация на енергия.
Форматът за време е hh:mm, като часовете са от интервала 00..24
Всяка отделна цифра е комбинация от различен брой сегменти [0..9]: 6,2,5,5,4,5,6,3,7,6.
Изход:
максимална консумация: 08:08 часа
минимална консумация: 11:11 часа
Решение

В едно училище празнуват годишнина. Решили да представят на едно табло всички награди, които сегашни и бивши ученици са получили.
Всяко свидетелство е правоъгълник, но с различен цвят и размери. Наложило се част от свидетелствата да се припокрият.
Да се състави програма, чрез която се въвеждат размерите на таблото и свидетелствата, както и тяхната позиция и цвят и се изведе на екрана как би изглеждало таблото. Каква комбинация от цветове би се получила вследствие различното разполжение на всеки отделен, различно оцветен правоълник.
Всички размери са естествени числа от интервала [1..60], а цветовете се въвеждат с букви.
Внимание! Допустимите размери на таблото се ограничават от размерите на екрана.
Решение

Иван много обича шах да играе, но е разсеян. Не винаги забелязва всички възможни ходове на коня и се притеснява за царицата си.
Да му помогнем.
Позициите в шахматната дъска са: по абсцисата от интервала [A..H], а по ординатата от интервала [1..8].
Да се състави програма, чрез която по въведени позиции на кон и царица се проверява дали има гунбеща комбинация - фигура да попада в бито от противника поле.
Пример: царица B3, кон A1 Изход: конят може да вземе царицата.
Решение

Нашият стар познат Иван си купил бус и основава спедиторска фирма - стоки разкарва от град на град.
Във всеки от градовете има различен брой контрагенти, като всеки от тях може да му предложи 1-4 вида стоки да транспортира до съседния град.
Като стигне до последния град взема стока и я кара в града си по същия маршрут.
Да се състави програма, която при въведено естествено число от интервала [10..84] извежда равнобедрен триъгълник от цифри - естествени числа от интервала [1..4] (брой стоки във всяка отделна фирма).
Всяка основа на триъгълника е с 1 по-дълга от предходната. Последното не се отнася само до последната основа - това са броя на фирмите във всеки отделен град.
Програмата да извежда броя възможни маршрути, както и възможните комбинации от стоки за транспортиране.
Пример: 13 Изход: брой маршрути 72.
Решение

Факториел от естествено число - N! може да се представи като произведение на всички естествени числа от интервала [1..N]. Аналогично представяне на N! може да се извърши и само като произведение на прости множители.
Пример: 5! = 120 = 2^3 * 3^1 * 5^1
Да се състави програма (C++), чрез която се въвежда естествено число N, изчислява се факториел и се извежда сумата от степенните показатели на търсените прости числа, негови множители. В горния пример търсената сума е 5.
Пример: N=6 Изход: 7
Решение

Да се състави програма (C++), чрез която се реализира популярна игра. Множеството елеманти са 3: камък, ножица, хартия. Отношението между елементите е следното: камък чупи ножица, ножица реже хартия, хартия покрива камък.
Потребителят въвежда последователно 3 цели числа [0..2].
За всяко въведено число компютърът генерира съответно друго цяло число от същия интервал.
Всяка двойка числа се сравнява поотделно и се извежда крайния резултат.
Пример: P=1,K=1; P=1,K=2; P=0,K=2 Изход: равни
Решение

N е естествено число от интервала [3..103] и представлява страна на куб.
Този куб е еднакво оцветен и се разрязва на малки кубчета със страна 1.
Да се състави програма, чрез която по въведено число N се извежда колко от малките кубчета ще бъдат съответно с по 3,2 и 0 оцветени страни.
Пример: 10 Изход: 8, 96, 512.
Решение

Училищата в един окръг решили да организират турнир по футбол на малки вратички. Схемата е "всеки срещу всеки".
Да се състави програма, чрез която по въведен брой отбори N - естествено число от интервала [2..255] се изчислява броя възможни срещи между отборите - като стойност на комбинация от съответен клас.
Пример: 25 Изход: 300.
Решение

Шефът на една фирма решил да направи парти като покани само ръководителите във фирмата и техните съпруги/съпрузи. Оказало се, че не всички са семейни и броят на мъжете не е непременно равен на броя жени.
При започване на партито всеки от гостите се поздравил с всички дошли на приема, като мъжете се ръкостискали с мъже, а жените с жени. Мъжете целували ръка на дамите.
Броят на жените е D, а на мъжете М, където D и М са естествени числа от интервала [2..255].
Да се състави програма, чрез която по въведени стойности за D и М се изчислява общия брой ръкостискания.
Пример: М=25, D=30 Изход: 735
Решение

Имате група от N момичета и N+1 момчета.
По колко различни начини могат да се подредят членовете на групата, ако всяко момиче трябва да бъде между две момчета?
Да се състави програма, чрез която по въведено естествено число N от интервала [2..8] за брой момичета се изчислява възможния брой подреждания на всички тази група, по указания начин.
Пример: N=4 Изход: 2880.
Решение

Да се състави програма, чрез която по въведено естествено съставно число N от интервала [10..1000] се търси най-малкото естествено число, за което произведението от всички негови цифри е равно на въведеното число N.
Ако въведем 512, то може да бъде получено като произведеие на 8*8*8, т.е числото 888.
Ако това не е възможно, да се изведе уведомяващо съобщение.
Пример: 672 Изход: 2678.
Решение

Иван и неговите 2 приятели събират календарчета и непрекъснато си ги обменят.
За лош късмет семейството на единия напуска града.
Събрали се тримата и колекцията делят, но нещо делбата не спори. Единият я разделя така: 3:4:5, втория 4:5:6, третия 5:6;7.
И тримата са единодушни: трябва да съществува пропорция между три съседни числа и всеки да получи равен брой.
Да се състави програма, чрез която последователно се въвеждат три естествени числа от интервала [1..20]. Програмата избира най-малкото число за търсената пропорция, извежда 3 съседни числа на пропорцията, както и общия брой календарчета, които се разпределят справедливо за всички.
Пример: 3,5,8 Изход: Общо: 648, 216 за всеки.
Решение

Имате две еднакви зарчета за игра. Двете са долепени едно до друго.
Да се състави програма, чрез която по въведени брой точки на стените, успоредни на долепените се извеждат възможната сума от точките на двете зарчета, видими по страните на формирания паралелепипед. В използвания алгоритъм опишете всяка възможна комбинация за брой точки.
Пример: 2,3 Изход: 33.
Решение

Имате 7 еднакви зарчета за игра, като 6 от тях са поставен плътно да всяка от страните на 7-мото зарче, т.е. всяка страна от вътрешното зарче е прилепена към страна от външно зарче.
Да се състави програма, която извежда броя възможни комбинации за брой точки по видимите страни на сформираната фигура от зарчета.
Решение

Нашият стар познат Иван отново е с математически проблеми, този път в комбинаторика. Трябва да реши тази задача: Ако има 3-цифрено естествено число, което може да има само цифри [1..3] колко числа могат да се формират – дори и с повторение на една и съща цифра.
Отива той при верния си приятел Великият мъдър смърф. Той изслушал внимателно условието, позасмял се и започнал да храни кокошките си мълчаливо. По едно време Иван не издържал – ако знаеш решението казвай, ако не да търся друг.
Великият мъдър смърф се усмихнал отново – Не чуваш ли всяка от кокошките изброява подред трите си любими храни, ама нали са кокошки една с една не съвпадат предпочитанията им. Отговорът е 27, но ти трябва да напишеш следната програма (C++).
Защо отговорът на смърфа е 27 и има ли възможност за извеждане на неправилна наредба на комбинациите, нашият герой тактично премълчава.
Да се състави програма, чрез която се въвежда естествено число [111..333], чиито цифри са само 1,2 или 3 (1- за жито, 2 – за леща, 3 – за просо) и се извеждат всички комбинации от 3-те думи: 1- за жито, 2 – за леща и 3 – за просо.
Пример: 121 Изход: 1) жито 2) леща 3) жито
Решение

Иван, по време на лятната си ваканция, е при дядо и баба на село. Там оглеждат кокошки по стара, но изпитана технология. Кокошките снасят яйцата в полог – слама свита като гнездо. Във всеки полог винаги стои по едно яйце. Полозите са разположени на различни места, като някои от тях са по-предпочитани - в смисъл, че повече яйца се снасят в тях. Броят на полозите е N, естествено число от интервала [3..10000].
Един ден Иван забелязал, че във всеки от полозите има различен брой яйца, но няма полог, в който яйцата са > N. Решил да направи следното: ще обикаля всички полози, като на всяка обиколка ще взема, ако разбира се това е възможно, еднакъв брой яйца от полог.
Той трябва също така да спазва технологията – във всеки полог винаги остава по едно яйце. Иван само взема яйца от полозите и никога не слага яйца от друг полог.
Имате N на брой редици, във всяка от като броят на елементите е различен и е от интервала [1..N]. На всяка отделна обиколка се изважда еднакъв брой елементи до изравняване броя на елементите във всяка от редиците. Да се състави програма, която по въведено естествено число N извежда най-малкия брой обиколки.
Пример: 5; 1,2,3,4,1 Изход: 3 обиколки
Решение

В супермаркет има N каси за обслужване на клиенти, плащащи в брой. Всяка каса обслужва средно по Mn клиента в минута.
Числата M1, M2..Mn, N са естествени от интервала [1..100].
Има само една опашка и всеки клиент сам избира свободната каса.
Да се изчисли вероятност - какво средно време на чакане [в секунди] е необходимо за всеки клиент, чакащ на такава обща опашка.
Пример: 2, 4, 6 Изход: 5.
Решение

Да се състави програма, чрез която се въвежда естествено число N [3..99], формира се редица от естествени числа [1..N]. Трябва да се изведе всяка пермутация, в която участват всички елементи в редицата.
Входни данни n - естествено число от интервала [1..99].
Пример: 3 Изход: 123,213,321,231,132,312
Решение

Анна и нейната приятелка са приети студентки в една и съща специалност, в един и същи институт и живеят в една стая.
И още нещо и двете много, ама много обичат шоколадови бонбони.
Изниква един проблем - кой да купи следващата доза удоволствие. Разбрали се за следното. Която не може да си вземе вече бонбон трябва да купи нова партида шоколадови бонбони и ги разпредели по видове в отделни купи.
Всяка може да си взема 0 или 1 бонбон от всеки вид, т.е. не е задължително да взема от всички налични видове. Изборът се въвежда като комбинация от последователно въведени 1 или 0, в зависимост дали се вземат шоколадови бонбони от дадена купа. Задължително трябва да се вземе поне 1 бонбон.
Да се състави програма, чрез която се прилага печеливша стратегия на компютър срещу Анна.
Броят купи и бонбоните във всяка купа са случайни естествени числа от интервала [3..9] и са предварително въведени.
Решение

Имало едно време две етърви, които много, много не се погаждали. Разправия ставала винаги, когато някоя от тях простирала пране. Все някоя се чувствала пренебрегната и без достатъчно място.
Имате простор с дължина естествено число от интервала [11..69].
Да се състави програма, която чрез диалог играе срещу потребителя. Посредством въпроси се въвежда желана позиция - начало и край при всеки ход на потребителя. Компютърът сам избира своя ход и то така, че да не загуби по обща дължина на позициите си.
Ходовете и на двамата противници са последователни. Всяки има право да избира позиция само във все още незаети места.
Играта продължава до изчерпване на свободното място или до отказ. Печели последният заел свободна позиция.
Решение

Върху окръжност с радиус R са означени N брой точки с различни, несъвпадащи координати. N е естествено число от интервала [3..103]. Всички точки са краища на отсечки - хорди в окръжността. Приема се, че всички точки са свързани с предходната и следващата точка.
Да се състави програма (C++), чрез която се въвежда естествено число N и се извежда общ брой различни отсечки, които се пресичат от една или повече други отсечки.
Пример: N = 6; Изход: 9
Решение

N е естествено число от интервала [3..103] и представлява брой точки с различни координати. Няма 3 точки, които да лежат на една права. Точките се разглеждат като върхове на триъгълници.
Да се състави програма (C++), чрез която се въвежда N и се извежда общ брой различни тригълници, чиито върхове са комбинация от произволни 3 точки
Пример: N = 4; Изход: 4
Решение

На равни интервали по абсцисата са разположени N на брой точки.
Да се състави програма, която чрез функция изчислява възможния брой формирани отсечки, чието начало и край съвпада с тези точки.
Входни данни естествено число N от интервала [3..1789].
Пример: 6 Изход: 15
Решение

Да се състави програма, чрез която се въвежда естествено число с брой цифри от интервала [5..45].
Програмата да изведе брой инверсии във въведеното число, т.е. колко цифри отляво надясно са по-малки от цифрата в текущата позиция за всяка една цифра от числото.
Програмата да извежда броя инверсии за всяка отделна цифра.
Пример: 1234321 Изход: 9.
Решение

Да се състави програма, която извежда всички възможни разбивания като суми на дадено естествено число от интервала [5..20].
Пример: 4 Изход: 4; 3+1; 2+2; 2+1+1; 1+1+1+1
Решение

Малката Мария се учи да бъде спестовна домакиня. Всяка попаднала й монета слага в спествната касичка и си събира капитал. Все пак ще прави купон за рожденния си ден.
Видове монети са: 1 лев, 50,20,10,5,2 и 1 стотинки. Броят на всяка монета от вид е цяло число [0..99].
Да се състави програма, чрез която се въвежда брой монети от вид и се извежда вероятност първата въведена в касата монета да е лев.
Пример: 80:1.00; 40:0.50; 35:0.20;45:0.10; 20:.05; 10:.02 10:.01 Изход: вероятност 2/3
Решение

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

В едно училище тече конкурс. Трябва да се сменят знаменосец и 2 асистентки. За следващият знаменосец няма спор - това си е отличнкът на випуска, многократен победител в няколко олимпиади. Проблемът е в избора на двете асистентки.
Надделява мнението, че от всичките N [10..110] класа трябва да се тегли жребий за избор на клас. Отговорниците на двата класа дават окончателното предложение на Педагогическия съвет.
След допълнителни дискусии вземат допълнително решение. В конкурса няма да участва класът на бъдещия знаменосец.
Да се състави програма, чрез която се въвежда N - брой класове и се извежда различни начина могат да се разпределят двете номинции.
Пример: N=23 Изход: 462
Решение

Пепа взе окончателно решение - преводач ще става. Дори и име за фирмата си измисли: Драгомани - агенция за превод и web дизайн. Но сегашният й проблем е нареждането на всички учебници, книги, речници и списания. Едно е ясно – двутомният английско-български речник ще е в средата, двата тома един до друг. Но останалите книги как да нареди?
В стаята влиза баща й, разбира проблема и се усмихва под мустак.
Съществува голям брой различни нареждания. В средата сложи двата тома, а отстрани нареди всички останали книги както искаш, по вид език, по цвят, по височина или дебелина. Избери си начин и нареждай.
Зад гърба им се усмихва брат й, той е съгласен с баща си, но поставя условие. Да избере които иска различни нареждания, но двата тома да не са един до друг .
Да се състави програма (C++) чрез която се въвежда N [5..105] за общ брой книги и M - начин на подреждане: 0) двутомният речник заедно и 1) двата тома разделени.
Пример: N=7 Изход: заедно 1440, поотделно 3600
Решение

Трима приятели са колекционери с различни хобита. Единият събира календарчета, вторият снимки на коли, а третият на футболисти.
Решили да се съберат заедно и всеки да разгледа колекцията на останалите.
За нас остава задачата, по колко различни начина всеки от приятелите може да си подреди колекцията, и по колко и тримата заедно.
Да се състави програма (C++), чрез която се въвеждат 3 естествени числа N,M,K [2..2002] и се извежда стойност на факториел за всяко от числата, както и факториел от сума на въведените числа.
Пример: 2,3,2 Изход 2,6,2, 5040
Решение

Да се състави програма, чрез която се въвежда естествено число N [2..1002].
Програмата да изведе изчислената стойност за факториел, представена в 10-ична и 2-ична бройни системи.
Да се изведе и отношение между цифрите 0 и 1.
Пример: N=14 Изход: 14!=87178291200 1010001001100001110110010100000000000, отношение 25/12
Решение

С цел подобряване екипната дейност на фирмата, нейната управа решава да проведе тиймбилдинг в едно курортно селище. В края на деня започва най-приятната част.
По желание на група танцьори дисководещият пуска дайчово хоро. На хорото се хващат 75% от колектива, всеки сам си избира къде.
Тук въпросът, не колко са различните начини за подреждане на участниците, а кои са първите 3 цифри на този брой и с колко нули завършва.
Да се състави програма, чрез която се въвежда N [10..310] за общ брой присъстващи, и се извеждат първите 3 цифри и броя десни нули за брой възможни нареждания на хорото.
Пример: 28 Изход: 243 - първите 3 леви цифри, 4 нули
Решение

Да се състави програма, чрез която се извършва обединение на две множества.
Въвеждат се две естествени числа N и M представляващи брои елементи в двете множества. М и N не са непременно равни. От клавиатурата се въвеждат съответния брой естествени числа от интервала [1..101]. Програмата да изведе като резултат обединение на две множества.
Пример:N=6 [2,3,4,4,3,2]; M=7 [1,2,3,4,5,6,7]
Изход: 7 елемента 2,3,4,1,5,6,7
Решение

Прочетена 4658 пъти Последно променена в Четвъртък, 27 Декември 2012 17:25