Написать программу определения количества шестизначных счастливых билетов

@kotd · Регистрация: 13.10.2014

Author24 — интернет-сервис помощи студентам

4. Написать программу определения количества шестизначных “счастливых”' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

Я решил задачу с помощью цикла. Как решить с помощью механизма рекурсии (ещё один метод) ?

C#

 static int HappyTicketsCycle ()
 
        {
            int a, a1, a2, a3, a4, a5;
            byte count = 0;
 
            for (a = 0; a <= 9; a++)
                for (a1 = 0; a1 <= 9; a1++)
                    for (a2 = 0; a2 <= 9; a2++)
                        for (a3 = 0; a3 <= 9; a3++)
                            for (a4 = 0; a4 <= 9; a4++)
                            {
                                a5 = (a + a1 + a2) - (a3 + a4);
 
                                if (a5 >= 0 && a5 <= 9)
                                    count += 1;
 
                            }
 
            return count;
        }
 
          
        
 
 
        static void Main(string[] args)
        {
            Console.WriteLine("Количество счастливых билетов: {0} ", HappyTicketsCycle()); //цикл
            HappyTicketsCycle();
        }

@~~MansMI~~ · 11.04.2015, 10:36

а не маловато счастливчиков?

C#

        static void Main(string[] args)
        {
            int count = 0;
            Console.BufferHeight = 4600;
            for (int n = 100001; n < 1000000; n++)
            {
                string s = n.ToString();
                if (s[0] + s[1] + s[2] == s[3] + s[4] + s[5])
                {
                    Console.Write(s + " ");
                    count++;
                    if (count % 11 == 0) Console.WriteLine();
                }
            }
            Console.WriteLine("\ncount={0}", count);
            Console.ReadKey(true);
        }

@valera_21 · 11.04.2015, 19:17

Сообщение от MansMI

а не маловато счастливчиков?

к вам такой же вопрос

@diadiavova · 11.04.2015, 21:31

Предложу свой вариант. Не рекурсия, но тоже ничего ))

C#

            Func<int, bool> isHappy = (int num) =>
                {
                    var digits = num.ToString("000000").Select(c => Int32.Parse(c.ToString()));
                    return (digits.Take(3).Sum() - digits.Skip(3).Sum()) == 0;
                };
            Console.WriteLine( (from int n in Enumerable.Range(0, 1000000) where isHappy(n) select n).Count());

@XRoy · 12.04.2015, 18:57

MansMI, diadiavova, Зачем тут вообще строки?

kotd, Рекурсивный вариант

C#

               public static void Main(string[] args)
        {
            int res = LuckyTicket(999999);
        }
 
        private static int LuckyTicket(int n)
        {
            if (n < 0) return 0;
            // Первые 3 цирфы
            int firstPart = n / 1000;
            // Вторые 3 цифры
            int secondPart = n % 1000;
 
            int fS = DigitsSum(firstPart);
            int sS = DigitsSum(secondPart);
 
            if (fS == sS) return 1 + LuckyTicket(n - 1);
            else return 0 + LuckyTicket(n - 1);
        }
 
 
        private static int DigitsSum(int n)
        {
            int ones = n % 10; // Единицы
            int tens = (n % 100) / 10; // Десятки
            int hundrens = n / 100; // Сотни
 
            return ones + tens + hundrens;
        }

Итеративный

C#

                public static void Main(string[] args)
        {
            int res = LuckyTicket(999999);
        }
 
        private static int LuckyTicket(int n)
        {
            int count = 0;
            for (int i = 0; i < n; n++)
            {
                // Первые 3 цирфы
                int firstPart = i / 1000;
                // Вторые 3 цифры
                int secondPart = i % 1000;
 
                int fS = DigitsSum(firstPart);
                int sS = DigitsSum(secondPart);
 
                if (fS == sS) count++;
            }
 
            return count;
        }
 
 
        private static int DigitsSum(int n)
        {
            int ones = n % 10; // Единицы
            int tens = (n % 100) / 10; // Десятки
            int hundrens = n / 100; // Сотни
 
            return ones + tens + hundrens;
        }

@~~MansMI~~ · 12.04.2015, 19:08

с рекурсией

C#

        static void Main(string[] args)
        {
            int count = 0;
            
            Console.BufferHeight = 5030;//если выводить номера
            SetChar(new char[6], 0, ref count);
            Console.WriteLine("\ncount={0}", count);
            Console.ReadKey(true);
        }
 
        static void SetChar(char[] s, int n, ref int count)
        {
            for (char ch = '0'; ch <= '9'; ch++)
            {
                s[n] = ch;
                if (n < 5) SetChar(s, n + 1, ref count);
                else
                    if (s[0] + s[1] + s[2] == s[3] + s[4] + s[5])
                    {
                        count++;
                        //если выводить номера
                        Console.Write(new string(s) + " ");
                        if (count % 11 == 0) Console.WriteLine();
                    }
            }
               
        }

@diadiavova · 12.04.2015, 19:13

Сообщение от XRoy

diadiavova, Зачем тут вообще строки?

Да собственно для наглядности. Я прекрасно понимаю, что с точки зрения той же производительности такой вариант не катит. Но так ли важна производительность в данном случае? Функция одноразовая и если будет сэкономлена секунда на вычисление, то что это даст? Ну вот такой вариант реализации IsHappy по производительности гораздо лучше

C#

        static bool IsHappy(int num)
        {
            int[] digits = new int[6];
            int divresult = num;
            for (int i = 0; i < 6; i++)
            {
                divresult = Math.DivRem(divresult, 10, out digits[i]);                
            }
            return (digits[0] + digits[1] + digits[2]) == (digits[3] + digits[4] + digits[5]);
        }

Но в наглядности он явно теряет. В первоначальном варианте хорошо видно, что число превращается в коллекцию цифр, которая превращается в коллекцию чисел и в конце концов сумма первых трех сравнивается с суммой последних трех. А что делается здесь - вообще без ста грамм не разберешься.

Добавлено через 1 минуту
И, кстати, вместо

C#

1	from int n in Enumerable.Range(0, 1000000) where isHappy(n) select n).Count()

Можно написать

C#

1	Enumerable.Range(0, 1000000).Count(IsHappy)

@kotd · 12.04.2015, 21:46 **[ТС]**

Спасибо) Вы тут ребята понаписывали, того что мы и не изучали даже

Будем разбираться

@~~MansMI~~ · 12.04.2015, 21:53

так обычно и бывает, один *** вопрос задаст, что и 10 мудрецов не разберутся

@kotd · 14.04.2015, 00:03 **[ТС]**

Кстати, маловато у меня было билетов, ибо не хватало { } . Щас переписал внимательно, столько же сколько у вас) 55252 ) Так что даже мой простой способ проканал , мудрецы) А вот с рекурсией надо разобраться

Добавлено через 6 минут
Хотя какие скобки. Там у count был тип byte . Вот в чём дело

Добавлено через 2 часа 27 минут
Process is terminated due to StackOverFlowException

@kolorotur · 14.04.2015, 10:00

Сообщение от kotd

Написать программу определения количества шестизначных “счастливых”' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.

Это число — константа, нет?

@valera_21 484 / 439 / 123 Регистрация: 05.01.2010 Сообщений: 1,848
	11.04.2015, 19:17	3
	Сообщение от MansMI а не маловато счастливчиков? к вам такой же вопрос 0

@kotd 0 / 0 / 0 Регистрация: 13.10.2014 Сообщений: 19
	12.04.2015, 21:46 [ТС]	8
	Спасибо) Вы тут ребята понаписывали, того что мы и не изучали даже Будем разбираться 0

@~~MansMI~~ Заблокирован
	12.04.2015, 21:53	9
	так обычно и бывает, один *** вопрос задаст, что и 10 мудрецов не разберутся 0

@kotd 0 / 0 / 0 Регистрация: 13.10.2014 Сообщений: 19
	14.04.2015, 00:03 [ТС]	10
	Кстати, маловато у меня было билетов, ибо не хватало { } . Щас переписал внимательно, столько же сколько у вас) 55252 ) Так что даже мой простой способ проканал , мудрецы) А вот с рекурсией надо разобраться Добавлено через 6 минут Хотя какие скобки. Там у count был тип byte . Вот в чём дело Добавлено через 2 часа 27 минут Process is terminated due to StackOverFlowException 0

@kolorotur 17684 / 12870 / 3365 Регистрация: 17.09.2011 Сообщений: 21,136
	14.04.2015, 10:00	11
	Сообщение от kotd Написать программу определения количества шестизначных “счастливых”' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр. Это число — константа, нет? 0