1.Arrays

01.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.

using System;

    class ArrayOf20Elements
    {
        static void Main(string[] args)
        {
            int[] array = new int[20];

            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine("Index {0} -> element {1}", i, array[i] = i * 5);
            }
        }
    }

02.Write a program that reads two arrays from the console and compares them element by element.

Обяснение:
Два масива са еднакви, когато дължината и елементите им са еднакви.

using System;

    class CompareTwoArrays
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the two array's: ");
            int arraysLength = int.Parse(Console.ReadLine());

            int[] firstArray = new int[arraysLength];
            int[] secondArray = new int[arraysLength];

            Console.WriteLine("Enter element's of the first array...");
            for (int i = 0; i < arraysLength; i++)
            {
                Console.Write("Enter number: ");
                firstArray[i] = int.Parse(Console.ReadLine());
            }

            Console.WriteLine("Enter element's of the second array... ");
            for (int i = 0; i < arraysLength; i++)
            {
                Console.Write("Enter number: ");
                secondArray[i] = int.Parse(Console.ReadLine());
            }

            //Compare elements of the two arrays
            for (int i = 0; i < arraysLength; i++)
            {
                if (firstArray[i] == secondArray[i])
                {
                    Console.WriteLine("{0} = {1}", firstArray[i], secondArray[i]);
                }
                if (firstArray[i] < secondArray[i])
                {
                    Console.WriteLine("{0} < {1}", firstArray[i], secondArray[i]);
                }
                if (firstArray[i] > secondArray[i])
                {
                    Console.WriteLine("{0} > {1}", firstArray[i], secondArray[i]);
                }
            }
            //Check if two arrays are EQUAL
            bool check = true;

            for (int i = 0; i < arraysLength; i++)
            {
                if (firstArray[i] != secondArray[i])
                {
                    check = false;
                    break;
                }
            }
            if (check == true)
            {
                Console.WriteLine("The two arrays are EQUAL!");
            }
            else
            {
                Console.WriteLine("The two arrays are NOT EQUAL!");
            }
        }
    }

03.Write a program that compares two char arrays lexicographically (letter by letter).

using System;

    class CompareTwoCharArraysLexicographically 
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the two arrays: ");
            int arraysLength = int.Parse(Console.ReadLine());

            char[] firstArray = new char[arraysLength];
            char[] secondArray = new char[arraysLength];

            Console.WriteLine("Enter elements of the first array...");
            for (int i = 0; i < arraysLength; i++)
            {
                Console.Write("Enter letter: ");
                firstArray[i] = char.Parse(Console.ReadLine());
            }

            Console.WriteLine("Enter elements of the second array...");
            for (int i = 0; i < arraysLength; i++)
            {
                Console.Write("Enter letter: ");
                secondArray[i] = char.Parse(Console.ReadLine());
            }

            int counterEven = 0;
            int counterFirst = 0;
            int counterSecond = 0;
            //Compare elements of the two arrays
            for (int i = 0; i < arraysLength; i++)
            {
                if (firstArray[i] == secondArray[i])
                {
                    Console.WriteLine("{0} = {1}", firstArray[i], secondArray[i]);
                    counterEven++;
                }
                if (firstArray[i] < secondArray[i])
                {
                    Console.WriteLine("{0} < {1}", firstArray[i], secondArray[i]);
                    counterFirst++;
                }
                if (firstArray[i] > secondArray[i])
                {
                    Console.WriteLine("{0} > {1}", firstArray[i], secondArray[i]);
                    counterSecond++;
                }
            }

            if ((counterEven > counterFirst) && (counterEven > counterSecond))
            {
                Console.WriteLine("The two arrays are EQUAL");
            }
            if ((counterFirst > counterEven) && (counterFirst > counterSecond))
            {
                Console.WriteLine("The first array is earlier than second array");
            }
            if ((counterSecond > counterEven) && (counterSecond > counterFirst))
            {
                Console.WriteLine("The second array is earlier than fitst array");
            }
        }
    }

04.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}.

Обяснение:
Стойностите на масива се въвеждат от потребителя. В началото текущата
поредица е 1. В цикъла за сравненията има една особеност, че
i < array.Length – 1. Това е така, за да не се излезе от границите на масива
и да се изпише грешка "Index was out of range&quot. Ако текущото число
е равно с предходното, текущата редица продължава и се определя най-добрата
редица. Ако текущото е различно от предходното, от него се започва нова редица.

using System;

    class MaximalSequenceOfEqualElements
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            Console.WriteLine("Enter elements of the array...");
            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Enter number: ");
                array[i] = int.Parse(Console.ReadLine());
            }

            int currentLen = 1;
            int bestLen = 0;
            int elements = 0;

            for (int i = 0; i < array.Length-1; i++)
            {
                if (array[i] == array[i+1])
                {
                    currentLen++;
                    if (currentLen > bestLen)
                    {
                        bestLen = currentLen;
                        elements = array[i];
                    }
                }
                else
                {
                    currentLen = 1;
                }
            }

            for (int i = 0; i < bestLen; i++)
            {
                Console.Write(elements);
            }
            Console.WriteLine();
        }
    }

05.Write a program that finds the maximal increasing sequence in an array.
Example: {3, 2, 3, 4, 2, 2, 4}  {2, 3, 4}.

Обяснение:
Задачата е аналогична на предходната.

using System;

    class MaximalIncreasingSequence
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the arrayaaaaa: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            Console.WriteLine("Enter elements of the array...");
            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Enter number: ");
                array[i] = int.Parse(Console.ReadLine());
            }

            int currentLen = 1;
            int bestLen = 0;
            int elements = 0;
            int start = 0;

            for (int i = 0; i < array.Length-1; i++)
            {
                if (array[i] < array[i+1])
                {
                    currentLen++;
                    if (currentLen > bestLen)
                    {
                        bestLen = currentLen;
                        elements = start;
                    }
                }
                else
                {
                    currentLen = 1;
                    start = i + 1;
                }
            }

            for (int i = elements; i < bestLen + elements; i++)
            {
                Console.WriteLine(array[i]);
            }
        }
    }

06.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.

using System;

    class FindElementsThatHaveMaximalSum
    {
        static void Main()
        {
            Console.Write("Enter N: ");
            int n = int.Parse(Console.ReadLine());

            int[] array = new int[n];

            Console.WriteLine("Enter elements of the array...");
            for (int i = 0; i < n; i++)
            {
                Console.Write("Enter number: ");
                array[i] = int.Parse(Console.ReadLine());
            }

            Console.Write("Enter K: ");
            int k = int.Parse(Console.ReadLine());

            if (k <= n)
            {
                int currentSum = 0;
                int maximalSum = 0;
                string currentNumbers = "";
                string numbers = "";

                for (int i = 0; i < array.Length; i++)
                {
                    if (i+k > array.Length)
                    {
                        break;
                    }
                    for (int j = i; j < i + k; j++)
                    {
                        currentSum += array[j];
                        currentNumbers = currentNumbers + " " + array[j];
                    }
                    if (currentSum > maximalSum)
                    {
                        maximalSum = currentSum;
                        numbers = currentNumbers;
                    }
                    currentSum = 0;
                    currentNumbers = " ";
                }
                Console.WriteLine("The numbers are: " + numbers);
                Console.WriteLine("The maximal sum is: " + maximalSum);
            }
            else
            {
                Console.WriteLine("ERROR!!! \"K\"  must be smaller than \"N\". Try again...");
                Main();
            }
        }
    }

07.Sorting an array means to arrange its elements in increasing order. Write a
program to sort an array. Use the “selection sort” algorithm: Find the smallest
element, move it at the first position, find the smallest from the rest, move it at
the second position, etc.

Обяснение:
Идея на алгоритъма: Намира най-малкия елемент в масива и го разменя с елемента, на първа позиция. След това, от останалите елементи, намира най-малкия и го разменя с този на втора позиция и т.н.

using System;

    class SelectionSortAlgorithm
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            Console.WriteLine("Enter elements of the array...");
            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Index {0} -> ", i);
                array[i] = int.Parse(Console.ReadLine());
            }

            int number = 0;
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = i+1; j < array.Length; j++)
                {
                    if (array[i] > array[j])
                    {
                        number = array[j];
                        array[j] = array[i];
                        array[i] = number;
                    }
                }
            }

            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
            } 
        }
    }

08.Write a program that finds the sequence of maximal sum in given array.
Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  {2, -1, 6, 4}. Can you do it with
only one loop (with single scan through the elements of the array)?

Обяснение:
Тук използвам алгоритъма на Кадан.
Идея на алгоритъма: масива се обхожда от ляво на дясно. Временната и максималната сума приемат стойнооста на първия елемент от масива. При всяко сумиране на числата се проверява стойностт на временната сума. Ако тя е по-голяма от максималната, запомнят се индексите на началния и крайния елемент и се определя стойността на максималната сума. Ако временната сума е по-малка от нула, следващото число става временна сума.

using System;

    class SequenceOFMaximalSumInGivenArray
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            Console.WriteLine("Enter elements of the array...");
            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Enter number: ");
                array[i] = int.Parse(Console.ReadLine());
            }

            int currentSum = array[0];
            int maxSum = array[0];
            int firstIndex = 0;
            int tempIndex = 0;
            int lastIndex = 0;

            for (int i = 1; i < array.Length; i++)
            {
                if (currentSum > 0)
                {
                    currentSum += array[i];
                    firstIndex = i;
                }
                else
                {
                    currentSum = array[i];
                    tempIndex = i;
                }
                if (currentSum > maxSum)
                {
                    maxSum = currentSum;
                    lastIndex = i;
                }
                firstIndex = tempIndex;
            }

            for (int i = firstIndex; i <= lastIndex; i++)
            {
                Console.WriteLine(array[i]);
            }
        }
    }

09.Write a program that finds the most frequent number in an array.
Example: {4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3}  4 (5 times)

Обяснение:
Задачата е подобана на предходната. Тук масива се сортира, се сравнява първя елемент със следващия. Има една особеност, че цикъла е от 0 до array.Length – 1. Това е така зада не се излезе от границите на масива и да се получи съобщение за грешка.

using System;

    class MostFrequentNumberInAnArray
    {
        static void Main(string[] args)
        {
            Console.Write("Enter length of the array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            Console.WriteLine("Enter elemnts of the array...");
            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Index {0} -> ", i);
                array[i] = int.Parse(Console.ReadLine());
            }

            Array.Sort(array);
            int currentLen = 1;
            int maximalLen = 0;
            int number = 0;
            int repeats = 1;

            for (int i = 0; i < array.Length-1; i++)
            {
                if (array[i] == array[i+1])
                {
                    currentLen++;
                    if (currentLen > maximalLen)
                    {
                        maximalLen = currentLen;
                        number = array[i];
                        repeats++;
                    } 
                }
                else
                {
                    currentLen = 1;
                }
            }
            Console.WriteLine("{0} -> {1} times", number, repeats);
        }
    }

10.Write a program that finds in given array of integers a sequence of given
sum S (if present). Example: {4, 3, 1, 4, 2, 5, 8}, S=11  {4, 2, 5}

Обяснение:
Задачата е подобна на предходните.

using System;

    class SequenceOfGivenSumInGivenArray
    {
        static void Main(string[] args)
        {
            Console.Write("Enter array length: ");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];

            for (int i = 0; i < arrayLength; i++)
            {
                Console.Write("Index {0} -> ", i);
                array[i] = int.Parse(Console.ReadLine());
            }

            Console.Write("Enter S: ");
            int s = int.Parse(Console.ReadLine());

            int currentSum = array[0];
            int firstIndex = 0;
            int lastIndex = 0;
            int startIndex = 0;

            for (int i = 0; i < array.Length-1; i++)
            {
                if (currentSum < s)
                {
                    currentSum += array[i + 1];
                    firstIndex = i;
                }
                if (currentSum > s)
                {
                    currentSum -= array[startIndex];
                    startIndex++;
                }
                if (currentSum == s)
                {
                    startIndex--;
                    lastIndex = i;
                    firstIndex = lastIndex - startIndex;  
                }
            }

            for (int i = firstIndex; i <= lastIndex; i++)
            {
                Console.WriteLine(array[i]);
            }
        }
    }

11.Write a program that finds the index of given element in a sorted array of
integers by using the binary search algorithm (find it in Wikipedia).

Обяснение:
Повече за binary search алгоритъма, или още казано двоично търсене, може да прочетете ТУК!

using System;

class BinarySearchAlgorithm
{
    static void Main(string[] args)
    {
        Console.Write("Enter array length: ");
        int arrayLength = int.Parse(Console.ReadLine());

        int[] array = new int[arrayLength];

        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("Index {0} -> ", i);
            array[i] = int.Parse(Console.ReadLine());
        }

        Console.Write("Enter number: ");
        int number = int.Parse(Console.ReadLine());

        Array.Sort(array);
        int left = 0;
        int right = array.Length - 1;
        int middle = 0;
        int index = 0;

        for (int i = 0; i < array.Length-1; i++)
        {
            middle = (left + right) / 2;

            if (number == array[middle])
            {
                index = middle;
                Console.WriteLine("The number index is: {0}", index);
                break;
            }
            if (number < array[middle])
            {
                right = middle - 1;
            }
            if (number > array[middle])
            {
                left = middle + 1;
            }
        }
        if (index != middle)
        {
            Console.WriteLine("There is no such number in the array!!!");
        }
    }
}

12. Write a program that creates an array containing all letters from the alphabet
(A-Z).Read a word from the console and print the index of each of its letters in the array.

using System;

class IndexOfEachLetter
{
    static void Main()
    {
        Console.Write("Enter word: ");
        string word = Console.ReadLine().ToLower();

        char[] englishAlphabet = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'g', 'k', 'l', 'm', 'n', 
                                     'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };

        foreach (char letter in word)
        {
            for (int i = 0; i < englishAlphabet.Length; i++)
            {
                if (letter == englishAlphabet[i])
                {
                    Console.WriteLine("Letter \"{0}\" index in array -> {1}", letter, i);
                }
            }
        }
    }
}

14.Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).

Обяснение:
Идея на алгоротъма: избира се главен елемент от масива, като всички елементи, които са по-малки от главния се поставят в ляво, а по-големите – в дясно. Рекурсивно се повтарят стъпките, като на края се прави конкатенация и се получава сортирания масив.

using System;

    class QuickSortAlgorithm
    {
        static void Quicksort(string [] elements, int left, int right)
        {
            int i = left;
            int j = right;
            string middle = elements[(left + right) / 2];
            while (i <= j)
            {
                while (elements[i].CompareTo(middle) < 0)
                {
                    i++;
                }

                while (elements[j].CompareTo(middle) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    // Swap
                    string tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive calls
            if (left < j)
            {
                Quicksort(elements, left, j);
            }

            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }

        static void PrintArray(string[] elements)
        {
            foreach (string element in elements)
            {
                Console.Write(element + " ");
            }
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            Console.Write("How many string elements you want to enter: ");
            int numberOfElements = int.Parse(Console.ReadLine());

            string[] elements = new string[numberOfElements];

            Console.WriteLine("Enter elements: ");
            for (int i = 0; i < numberOfElements; i++)
            {
                Console.Write("Enter string: ");
                elements[i] = Console.ReadLine();
            }

            int left  = 0;
            int right = elements.Length - 1;

            Console.Write("The unsorted array looks like: ");
            PrintArray(elements);
            Quicksort(elements, left, right);
            Console.Write("The sorted array looks like: ");
            PrintArray(elements);
        }
    }

15. Write a program that finds all prime numbers in the range [1…10 000 000].
Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

Обяснение:
Идея на алгоритъма: започва се от числото 2 и се премахват всички останали, който се делят без остатък на 2. След това се взима 3 и се премахват всички останали, които се делят без остатък на 3 и т.н.

using System;

  class SieveOfEratosthenesAlgorithm
    {
        static void Main(string[] args)
        {
            Console.Write("Enter array legth:");
            int arrayLength = int.Parse(Console.ReadLine());

            int[] array = new int[arrayLength];
            int max = (int)Math.Sqrt(arrayLength);

            for (int i = 2; i < max; i++)
            {
                if (array[i] == 0)
                {
                    for (int m = (i * i); m < arrayLength; m += i)
                    {
                        array[m] = 1;
                    }
                }
            }

            for (int i = 2; i < arrayLength; i++)
            {
                if (array[i] == 1) continue;
                if (i > 2) Console.Write(",");
                Console.Write("{0}", i);
            }
            Console.WriteLine("");
        }
    }

20. Write a program that reads two numbers N and K and generates all the variations
of K elements from the set [1..N]. Example: N = 3, K = 2  {1, 1}, {1, 2}, {1, 3},
{2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}

Обяснение:
Използва се рекурсивен метод, който върти индекса на масива. Алгоритъма спира да работи, когато индекса стане равен на дължината на масива и се отпечата резултата. В противен случай, метода се извиква рекурсивно и всеки път индекса увеличава стойността си с едниница.

using System;

    class GenerateVariationsOfElements
    {
        static void Variations(int[] array, int n, int index)
        {
            if (index == array.Length)
            {
                for (int i = 0; i < array.Length; i++)
                {
                    Console.Write(array[i] + " ");
                }
                Console.WriteLine();
            }

            else
            {
                for (int i = 1; i <= n; i++)
                {
                    array[index] = i;
                    Variations(array, n, index + 1);
                }
            }
        }

        static void Main()
        {
            Console.Write("Enter N: ");
            int n = int.Parse(Console.ReadLine());

            Console.Write("Enter K: ");
            int k = int.Parse(Console.ReadLine());

            int[] array = new int[k];

            Variations(array, n, 0);
        }
    }

21. Write a program that reads two numbers N and K and generates all the
combinations of K distinct elements from the set [1..N]. Example: N = 5, K = 2 
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}

Обяснение:
Задачата е подобна на предходната. Разликата е в това, че се използва допълнителна променлива tempNumber, която показва от къде да започне да се ибягват повторенията.

using System;

    class GeneratesAllCombinations 
    {
        static void Combinations(int[] array, int n, int index, int tempNumber)
        {
            if (index == array.Length)
            {
                for (int i = 0; i < array.Length; i++)
                {
                    Console.Write(array[i] + " ");
                }
                Console.WriteLine();
            }

            else
            {
                for (int i = tempNumber; i <= n; i++)
                {
                    array[index] = i;
                    Combinations(array, n, index + 1, i+1);
                }
            }
        }

        static void Main(string[] args)
        {
            Console.Write("Enter N: ");
            int n = int.Parse(Console.ReadLine());

            Console.Write("Enter K: ");
            int k = int.Parse(Console.ReadLine());

            int[] array = new int[k];

            Combinations(array, n, 0, 1);
        }
    }
Advertisements

3 responses to “1.Arrays

  1. Задача 11: не знам къде точно е грешката. Направил съм типична реализация на binary search алгоритъма. Посочи къде точно в кода ми е грешката.

    Задача 12: вместо “j” съм написал “g”, ще го оправя. Благодаря за оточнението. Но все пак по-важен е самия код 🙂

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s