Като се има предвид набор от градове и разстояние между всяка двойка градове, проблемът е да се намери най -кратката възможна обиколка, която посещава всеки град точно веднъж и се връща в началната точка.
Проблем: Като се има предвид 2 процес I и J, трябва да напишете програма, която може да гарантира взаимно изключване между двете без допълнителна хардуерна поддръжка.
Генериране на произволни сортирани масиви Ние съхраняваме елементите на произволни масиви в масив и след това го сортираме и отпечатаме.
Дадено е число „n“ и n числа, сортирайте числата с помощта на едновременно сортиране чрез сливане. (Съвет: Опитайте се да използвате системни извиквания shmget, shmat). Част 1: Алгоритъмът (КАК?) Рекурсивно направете два дъщерни процеса, един за лявата половина, един за дясната половина. Ако броят на елементите в масива за даден процес е по-малък от 5, изпълнете сортиране чрез вмъкване. След това родителят на двете деца обединява резултата и се връща обратно към родителя и т.н. Но как да го направите едновременно? Част 2: Логичното (ЗАЩО?) Важната част от решението на този проблем не е алгоритмично, а да обясни концепциите за операционна система и ядро. За да постигнем едновременно сортиране, имаме нужда от начин да накараме два процеса да работят върху един и същ масив едновременно. За да улесни нещата, Linux предоставя много системни извиквания чрез прости крайни точки на API. Две от тях са shmget() (за разпределение на споделена памет) и shmat() (за операции със споделена памет). Създаваме споделено пространство в паметта между дъщерния процес, който разклоняваме. Всеки сегмент е разделен на ляво и дясно дете, което е сортирано, като интересното е, че те работят едновременно! Shmget() изисква от ядрото да разпредели споделена страница и за двата процеса. Защо традиционният fork() не работи? Отговорът се крие в това какво всъщност прави fork(). От документацията „fork() създава нов процес чрез дублиране на извикващия процес“. Дъщерният процес и родителският процес се изпълняват в отделни пространства на паметта. По време на fork() и двете пространства на паметта имат едно и също съдържание. Записите в паметта, промените на файловия дескриптор (fd) и т.н., извършени от един от процесите, не засягат другия. Следователно имаме нужда от споделен сегмент на паметта.
Даден е масив от положителни цели числа, заменете всеки елемент в масива така, че разликата между съседни елементи в масива да е по-малка или равна на дадена цел. Трябва да минимизираме цената на корекцията, която е сумата от разликите между новите и старите стойности. По принцип трябва да минимизираме ?|A[i] - Anew[i]| къде 0? аз? n-1, n е размерът на A[] и Anew[] е масивът със съседна разлика, по-малка или равна на целта. Да приемем, че всички елементи на масива са по-малки от константата M = 100.
Предпоставки: BIT, DFS
Дадено е цяло число n, представляващо броя на цифрите. Задачата е да се отпечатат всички n-цифрени числа, така че абсолютната разлика между сбора на цифрите на четни и нечетни позиции да е точно 1. Забележка: Числото не трябва да започва с 0 (не се допускат водещи нули).
Дадено е просто дърво на изрази, състоящо се от основни двоични оператори, т.е. + , - ,* и / и някои цели числа, оценете дървото на изрази.
При даден брой цифри n, отпечатайте всички n-цифрени числа, чийто сбор от цифри дава даден сбор. Решението не трябва да разглежда водещите нули като цифри. Примери:
Дадени са два масива с цели числа, добавете елементите им в третия масив, като удовлетворите следните ограничения -
Даден е масив от цели числа, намерете дали е възможно да премахнете точно едно цяло число от масива, който разделя масива на два подмасива с една и съща сума.
Даден е масив, който съдържа както положителни, така и отрицателни цели числа, намерете произведението на максималния продуктов подмасив. Очакваната времева сложност е O(n) и може да се използва само O(1) допълнително пространство.
Даден е масив arr[] и цяло число k, намерете масива след обръщане на всеки подмасив от последователни k елемента на място. Ако последният подмасив има по-малко от k елемента, обърнете го както е. Променете масива на място, не връщайте нищо.
Даден е списък от цели числа, пренаредете списъка така, че да се състои от редуващи се минимални максимални елементи, като използвате само операции със списък. Първият елемент от списъка трябва да е минимален, а вторият елемент трябва да е максимален от всички елементи, присъстващи в списъка. По същия начин третият елемент ще бъде следващият минимален елемент, а четвъртият елемент е следващият максимален елемент и така нататък. Използването на допълнително пространство не е разрешено. Примери:
Даден е диапазон [n,m], намерете броя на елементите, които имат нечетен брой фактори в дадения диапазон (n и m включително). Примери:
Даден е двоичен масив с размер n, където n > 3. Вярна (или 1) стойност в масива означава активен, а false (или 0) означава неактивен. Дадено е число k, задачата е да се намери броя на активните и неактивните клетки след k дни. След всеки ден състоянието на i-та клетка става активно, ако лявата и дясната клетка не са еднакви и неактивно, ако лявата и дясната клетка са еднакви (и двете 0 или и двете 1).
Даден е масив от n уникални цели числа, където всеки елемент в масива е в диапазона [1, n]. Масивът има всички различни елементи и размерът на масива е (n-2). Следователно две числа от диапазона липсват в този масив. Намерете двете липсващи числа.
Даден е сортиран масив от n равномерно разпределени стойности arr[], напишете функция за търсене на определен елемент x в масива. Линейното търсене намира елемента за O(n) време, Jump Search отнема O(n) време и двоичното търсене отнема O(log n) време. Интерполационното търсене е подобрение спрямо двоичното търсене за екземпляри, където стойностите в сортиран масив са равномерно разпределени. Интерполацията конструира нови точки от данни в обхвата на дискретен набор от известни точки от данни. Двоичното търсене винаги отива до средния елемент за проверка. От друга страна, търсенето с интерполация може да отиде на различни места според стойността на ключа, който се търси. Например, ако стойността на ключа е по-близо до последния елемент, търсенето с интерполация вероятно ще започне търсене към крайната страна. За да се намери позицията, която ще се търси, се използва следната формула.
Даден е масив от n различни елемента. Намерете максимума на произведението на минимума на две числа в масива и абсолютната разлика на техните позиции, т.е. намерете максималната стойност на abs(i - j) * min(arr[i], arr[j]), където i и j варират от 0 до n-1.
Даден е масив, съдържащ положителни и отрицателни числа. Масивът представлява контролни точки от единия до другия край на улицата. Положителните и отрицателните стойности представляват количество енергия в тази контролна точка. Положителните числа увеличават енергията, а отрицателните числа намаляват. Намерете минималната първоначална енергия, необходима за пресичане на улицата, така че енергийното ниво никога да не стане 0 или по-малко от 0.
