Курсы по программированию

Формула программиста
основатель — Волосатов Евгений Витольдович

Комбинаторика / Комбинаторика. Счастливые билеты N

  • На этом уроке мы рассмотрим
    два основных способа решения комбинаторных задач:
    Первый способ - когда известно количество объектов - вложенные циклы.
    Второй способ - любое количество объектов - использование рекурсии.

    Задание:
    Решить задачу «Счастливые билеты N».
    Скачать книжку для чтения по комбинаторике:
    Как решать комбинаторные задачи.
  • Дата отправки отчёта: 17 февраля
  • Задание выполнено: за 3 час. 00 мин.
  • Чему научился: Работе с массивами, решил задачу в общем виде.
  • Что было сложным: Решить математически. Здесь уже не рекурсия, иначе программа будет работать очень долго.
  • Комментарии: Всё-таки, решил сделать программу, решающую задачу для довольно больших N.

        class Program
        {
            static void Main(string[] args)
            {
                long[] sum, sum2;
                long S = 0;
                int N;

                N = int.Parse(Console.ReadLine());
                sum = new long[9 * N + 1];
                sum2 = new long[9 * N + 1];
                for (int i = 0; i <= 9*N; ++i)
                    sum[i] = 0;
                for (int i = 0; i <= 9; ++i)
                {
                    sum[i] = 1;
                    sum2[i] = 1;
                }

                if (N > 1)
                    for (int k = 2; k <= N; ++k)
                    {
                        for (int i = 0; i <= 9 * k; ++i)
                        {
                            switch (i)
                            {
                                case 0: sum[i] = 1; break;
                                case 1:
                                case 2:
                                case 3:
                                case 4:
                                case 5:
                                case 6:
                                case 7:
                                case 8:
                                case 9: sum[i] += sum[i - 1]; break;
                                case 10: sum[i] += sum[i - 1] - sum[i - 10]; break;
                                default: sum[i] += sum[i - 1] - sum2[i - 10]; break;
                            }
                            Console.Write("{0,2:D}, ", sum[i]);
                        }
                        sum.CopyTo(sum2, 0);
                        Console.WriteLine();
                        Console.WriteLine();
                    }

                for (int i = 0; i <= 9 * N; ++i)
                    S += sum[i] * sum[i];

                Console.WriteLine(S);
                Console.ReadKey();

                //for (int a = 0; a < 10; ++a)
                //    for (int b = 0; b < 10; ++b)
                //        for (int c = 0; c < 10; ++c)
                //            for (int d = 0; d < 10; ++d)
                //                for (int e = 0; e < 10; ++e)
                //                    for (int f = 0; f < 10; ++f)
                //                        if (a + b + c == d + e + f)
                //                            console.writeline("{0} {1} {2} {3} {4} {5}", a, b, c, d, e, f);
            }
        }
  • Оценка видео-уроку:
Отчёт от 7980 за Комбинаторика / Комбинаторика. Счастливые билеты N




Оцени работу

 
Сохранить страницу:

7980. Сергей Лузум
Сергей Лузум
ответить
# Комбинаторика / Комбинаторика. Счастливые билеты N / 2016-02-17 13:11

Чуть-чуть доработал:
namespace Combinatorics
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] sum, sum2;// Массивы, хранящие количество комбинаций из N цифр для каждой возможной суммы цифр (диапазон 0..9*N)
            long S = 0;
            int N;

            N = int.Parse(Console.ReadLine());
            sum = new long[9 * N + 1];
            sum2 = new long[9 * N + 1]; //Здесь будем хранить значения для предыдущего N
           
            for (int i = 0; i <= 9*N; ++i)//Для N == 1 заполняем массив вручную
                if (i < 10)
                    sum[i] = 1;
                else
                    sum[i] = 0;

            if (N > 1)
                for (int k = 2; k <= N; ++k)
                {
                    sum.CopyTo(sum2, 0);
                    for (int i = 1; i <= 9 * k; ++i)
                        if (i < 10)
                            sum[i] += sum[i - 1];
                        else
                            sum[i] += sum[i - 1] - sum2[i - 10];
                }

            for (int i = 0; i <= 9 * N; ++i)//Считаем количество счастливых билетов для 2*N цифр
                S += sum[i] * sum[i];

            Console.WriteLine(S);
            Console.ReadKey();
        }
    }
}


  • Отчёт оценивали:
    1537Сергей+1   4004Елена+1   6925Артём+1   8886Михаил Ермишин+1   8275Tekashnik+1   4992Николай+1   7645Александр Львович+1   2624Макс0   5649Максим Лапшинов+1   5760Мариша +1   791Валерий+1   1Евгений Витольдович+1   2773Никита+1   7157muxasio+1   2639Морозов Юрий Александрович+1   689Igorenzia+1   459Сергей Сергеевич+1   2721mikemet+1   5026Екатерина+1   1947Denis+1   4467Alcatraz+1  

Начинаем практику по языку C#




Чтобы стать хорошим программистом — нужно писать программы. На нашем сайте очень много практических упражнений.

После заполнения формы ты будешь подписан на рассылку «C# Вебинары и Видеоуроки», у тебя появится доступ к видеоурокам и консольным задачам.

Несколько раз в неделю тебе будут приходить письма — приглашения на вебинары, информация об акциях и скидках, полезная информация по C#.

Ты в любой момент сможешь отписаться от рассылки.
Научился: Глубже проработал приемы работы с рекурсией. Интересен вызов рекурсивной функции в цикле. Очень показательна оптимизация алгоритма.
Трудности: Сложность возникла одна: в роботе Шарп не прошел тест 4 по тайм ауту.
Очень приличный урок, он мне много дал. Материал объясняется превосходно, черпай - не ленись. Еще более стали понятны плюсы и минусы рекурсии. Огромное спасибо за урок, Евгений Витольдович!
Научился: Получил лучшее понимания рекурсии, узнал об оптимизации, решил интересную задачу.
Трудности: Сложностей не возникло.
Спасибо за урок.