В тази тема ще поместя, част от решенията на задачите от Лекцията за масиви.
Задача 1. Write a program that allocates array of 20 integers and initializes each element by its index multiplied by 5. Print the obtained array on the console.
Решение: PasteBin
Обяснение: Доста праволинейна задача като по мое лично мнение, най-подходящо тук е да използваме for цикъл. Защо? Ами нужно ни е да знаем индекса на масива и инициализацията на отделните елементи става много лесно, като просто умножим брояча на for цъкала по 5 и го присвоим към дадения елемент.
Задача 2: Write a program that reads two arrays from the console and compares them element by element.
Решение: PasteBin
Обяснение: Относително лесна задача, като първите няколко стъпки са доста праволинейни – попълваме 2 масива, чрез for цикли и четене на отделните елементи от конзолата. Същинската част е след това.
Инициализираме bool променлива която индикира дали дадени два елемента си равни ( началната и стойност е true т.к. двата масива са равни до доказване на противното ). След това обхождаме 2та масива едновременно ( с помощта на индекса на for цикъла, който индикира кореспондиращия индекс в 2та масива ) и ако някой от двата елемента не са равни, то променяме стойността на bool променливата на false и break-ваме цикъла. Защо го break-ваме ? Ами за нас е достатъчно, че 2 елемента са различни за да заключим, че двата масива са различни.
Задача 3: Write a program that compares two char arrays lexicographically (letter by letter).
Решение: PasteBin
Обяснение: Основната логика, тук е – първо проверяваме дали двата масива имат равна дължина, ако не то те не са равни. Ако има равна дължина проверяваме по отделно всеки елемент и ако има даже един различен двата масива не са равни.
Задача 4: Write a program that finds the maximal sequence of equal elements in an array. Example: {2, 1, 1, 2, 3, 3, 2, 2, 2, 1} -> {2, 2, 2}.
Решение: PasteBin
Обяснение: Използвал си 3 променливи, за следните цели:
len – текущата дължина на проверяваната редица.
bestLen – най-голяма дължина срещана до сега;
bestLenElement – елемента, който се е срещал най-много до сега.
След това обхождам масива си от ляво на дясно и започвам да проверявам дали текущия елемент е равен на следващия ( myArray[i] == myArray[i+1] ). Ако да увеличавам дължината на текущата редичка, ако не проверявам дали дължината на текущата редица е по-голяма от най-голямата до сега. Ако е така, присвоявам bestLen = len; и отбелязван, на кой елемент съм за bestLenElement .
Следващата стъпка е да ресетна len на 1.
И накрая, се подсигурявам, че последната редица не е била, най-голямата т.к. това е случай, който се изпуска от for цикъла ми.
Забележка: Защо len=1; ? Ами понеже елемента който сравняваме със следващия е редичка сам за себе си с дължина 1.
Забележка 2: Не забравяйте при задаване на условието на цъкал то, да е с едно по-малко от максималното ( myArray.Length-1 ) т.к. проверяваме с 1 елемент напред и ако не счетем това ще имаме IndexOutOfRange изключение.
Задача 5: Write a program that finds the maximal increasing sequence in an array. Example: {3, 2, 3, 4, 2, 2, 4} -> {2, 3, 4}.
Решение: PasteBin
Обяснение: Логиката тук е аналогична с тази от 4та задача, с малки изключения. Условието при което увеличаваме дължината на текущата редица е следващия елемент да е по-голям от текущия и вместо да взимаме на-добрия елемент, взимаме последния елемент от редицата и чрез него си принтваме цялата на-добра редичка, чрез намаляващ for.
Задача 6: Write a program that reads two integer numbers N and K and an array of N elements from the console. Find in the array those K elements that have maximal sum.
Решение: PasteBin
Обяснение: Доста интресна задачка. Основната ми логика тук е:
Първия for цикъл обикаля по отделните елементи на масива.
Когато влезем в този for имаме следната проверка: (i + k > arrayLen) т.е. дали к елемента ( дължината на търсената редица ) напред няма да излезем извън нашия масив т.е. ако е вярно няма смисъл да правим други проверки и за това break; – ваме цикъла.
Следва същинската проверка за сумата с втори for цикъл , който върти до i + k – дължината на търсената ни редица от елемента на който сме.
След това просто имаме проверка дали, текущата сума е по-голяма от най-голямата сума до сега. Ако да заместваме най-голямата сума до сега с нея.
И накрая нулираме текущата сума.
Очаквайте, скоро Част втора от домашната за масиви 🙂
Теодоре, пробвай на пета задача с този масив да видиш какъв резултат дава:
2, 2, 2, 1, 2, 3, 5, 6, 7, 8, 9, 10, 2, 1, 2, 3, 4, 4
1, 2, 3, 5, 6, 7, 8, 9, 10, – мисля, че това трябва да е.
Пак, не се изразих както трябва – това който постнах ми изкарва.
Така е, това изкарва, което какво значи – че не бачка, правилно, щото 3 и 5 не да последователни числа.
Ами, тук зависи какво разбираш под:
Write a program that finds the maximal increasing sequence
Аз разбирам просто да се увеличава, не да е със стъпка 1. Но иначе ще питам, аз след малко имам лекция 🙂
И аз съм в залата, от лявата страна след средата, ти къде си? 😀
И аз от лявата, на 4тия ред 🙂
Иначе си прав за масива, аз съм се объркал.
Може и да се прав, зависи какво са имали предвид авторите 🙂
Точно зад теб през един ред съм 😀
Трудно ще те позная 😀 Ти после от асистените ли си ?
Не съм, щи се обадя след лекция 🙂
За шеста задача в условието пише “Find in the array those K elements that have maximal sum.” т.е. никъде не се казва тези елементи да са последователни!
Правя ги последователни, единство поради причината че после в следващите задачи има такава при който се иска да се намери на непоследователни.
И аз съм на мнението на loloto, ама тоя път реших да не се обаждам неподготвен 🙂
Ако искате, може да го направите и с непоследователни елементи ( имайте предвид, че така става доста по-трудно ). Но лично не виждам смисъл да правя една и същата задача 2 пъти 🙂
Че що по-трудно – срртираш си масива и взимаш последните K елементи и си в бизнеса?
Хах ! За това не бях се сетил интересна идея, аз щях да генерирам всички подмножества и да търся от там 😀
Е, Теодоре, не четеш решенията на другите, разгоря се дискусия, че Array.Sort() било бавно. 🙂
Aaa чета, чета – гледах че е с 20 пъти в по бавно, но тук не търсим колко е бързо а да бачка 😀 Иначе не съм сигурен колко ще е бързо с пълна генерация на подмножества при 10 елемента ще трябва да генерираме 1023 подмножества, но пък аз ги намирам побитово така, че не е много бавно. Трябва да се тества за да се види кое е по-добро 🙂
Мдааа, побитови операции, определено който ги владее има сериозно предимство. Ти имаш ли някакво правило кога ползваш побитови операции или ти е до усет/опит?
Честно, казано аз, почти винаги ги избягва т.к. просто не ги обичам много, много, пък и не ги владея :). Конкретно тук мога да ги използвам т.к. Николай Костов ни обяснява как точно се намират всички подмножества от множество, побитово. Ако ти е интересно, пуснал съм доста подробно обяснение в 16 задача във форума 🙂
Мерси, ще погледна.
Аз първо я направих побитово и повярвай ми дооооста е бавна. Все пак там сложността на алгоритъма расте доста бързо с нарастване на N и К. Чак после се сетих за сортировката 🙂 Иначе със сортиране, ако трябва да сме напълно коректни трябва да запазим първоначалните индекси някакси (С копиране на масива). Също ако 2 комбинации дават еднаква сума не е много ясно какво правим 😛
Защо трябва да пазим първоначалната индексация ?
За коя задача става въпрос ?
За 6-та
“loloto January 11, 2013 at 19:29
Аз първо я направих побитово и повярвай ми дооооста е бавна. Все пак там сложността на алгоритъма расте доста бързо с нарастване на N и К. Чак после се сетих за сортировката Иначе със сортиране, ако трябва да сме напълно коректни трябва да запазим първоначалните индекси някакси “
6-та дава грешен изход при отрицателни числа в масива !
Това е заради нулирането на текущата сума при всяка итерация, което автоматично я прави по-голяма от максималната сума.
sorry, моя грешка