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

Формула программиста
основатель — Волосатов Евгений Витольдович
Вебинар «Что тебе мешает стать крутым программистом?» начнётся через 2 дня 08 мин.

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

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

    Задание:
    Решить задачу «Счастливые билеты N».
    Скачать книжку для чтения по комбинаторике:
    Как решать комбинаторные задачи.
  • Дата отправки отчёта: 17 февраля 2016 г.
  • Задание выполнено: за 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#.

Ты в любой момент сможешь отписаться от рассылки.
Научился: Я узнал как рассчитывать количество счастливых билетов неопределённой длинны
В консоли всё работает, но вот робот Шарп меня не проверяет. Отличный урок! Мне он очень понравился :~)
Научился: Применению вложенных циклов при известном числе параметров и рекурсии - при неизвестном их кол-ве.
Трудности: Вникнуть в рекурсию )
Так и не смог "обмануть" робота C# . В студии при выборе N от 1 до 5 отрабатывает на ура . Робот же - не принимает .