Домашни от масиви – решения и обяснения. Част първа.

C-To-Go-300x300

В тази тема ще поместя, част от решенията на задачите от Лекцията за масиви.

Задача 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 – дължината на търсената ни редица от елемента на който сме.

След това просто имаме проверка дали, текущата сума е по-голяма от най-голямата сума до сега. Ако да заместваме най-голямата сума до сега с нея.

И накрая нулираме текущата сума.

Очаквайте, скоро Част втора от домашната за масиви 🙂

Advertisements

29 thoughts on “Домашни от масиви – решения и обяснения. Част първа.

  1. Теодоре, пробвай на пета задача с този масив да видиш какъв резултат дава:

    2, 2, 2, 1, 2, 3, 5, 6, 7, 8, 9, 10, 2, 1, 2, 3, 4, 4

      • Така е, това изкарва, което какво значи – че не бачка, правилно, щото 3 и 5 не да последователни числа.

      • Ами, тук зависи какво разбираш под:
        Write a program that finds the maximal increasing sequence
        Аз разбирам просто да се увеличава, не да е със стъпка 1. Но иначе ще питам, аз след малко имам лекция 🙂

  2. За шеста задача в условието пише “Find in the array those K elements that have maximal sum.” т.е. никъде не се казва тези елементи да са последователни!

    • Правя ги последователни, единство поради причината че после в следващите задачи има такава при който се иска да се намери на непоследователни.

      • Ако искате, може да го направите и с непоследователни елементи ( имайте предвид, че така става доста по-трудно ). Но лично не виждам смисъл да правя една и същата задача 2 пъти 🙂

      • Че що по-трудно – срртираш си масива и взимаш последните K елементи и си в бизнеса?

      • Хах ! За това не бях се сетил интересна идея, аз щях да генерирам всички подмножества и да търся от там 😀

      • Е, Теодоре, не четеш решенията на другите, разгоря се дискусия, че Array.Sort() било бавно. 🙂

      • Aaa чета, чета – гледах че е с 20 пъти в по бавно, но тук не търсим колко е бързо а да бачка 😀 Иначе не съм сигурен колко ще е бързо с пълна генерация на подмножества при 10 елемента ще трябва да генерираме 1023 подмножества, но пък аз ги намирам побитово така, че не е много бавно. Трябва да се тества за да се види кое е по-добро 🙂

      • Мдааа, побитови операции, определено който ги владее има сериозно предимство. Ти имаш ли някакво правило кога ползваш побитови операции или ти е до усет/опит?

      • Честно, казано аз, почти винаги ги избягва т.к. просто не ги обичам много, много, пък и не ги владея :). Конкретно тук мога да ги използвам т.к. Николай Костов ни обяснява как точно се намират всички подмножества от множество, побитово. Ако ти е интересно, пуснал съм доста подробно обяснение в 16 задача във форума 🙂

      • Аз първо я направих побитово и повярвай ми дооооста е бавна. Все пак там сложността на алгоритъма расте доста бързо с нарастване на N и К. Чак после се сетих за сортировката 🙂 Иначе със сортиране, ако трябва да сме напълно коректни трябва да запазим първоначалните индекси някакси (С копиране на масива). Също ако 2 комбинации дават еднаква сума не е много ясно какво правим 😛

      • За 6-та
        “loloto January 11, 2013 at 19:29
        Аз първо я направих побитово и повярвай ми дооооста е бавна. Все пак там сложността на алгоритъма расте доста бързо с нарастване на N и К. Чак после се сетих за сортировката Иначе със сортиране, ако трябва да сме напълно коректни трябва да запазим първоначалните индекси някакси “

  3. 6-та дава грешен изход при отрицателни числа в масива !
    Това е заради нулирането на текущата сума при всяка итерация, което автоматично я прави по-голяма от максималната сума.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s