Рекурсия: подсчет количества четных цифр числа (на С)

@Do6oDyH · Регистрация: 25.10.2010

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

Написать рекурсивную функцию считывающую количество четных цифр числа.

Плохо понял рекурсию объясните на этом примере пожалуйста.

silent_1991 · 18.04.2011, 15:27

Эх, люблю я тернарный оператор)))

C

#include <stdio.h>
 
size_t count_even_digits(int);
 
int main(void)
{
    int number;
 
    printf("Enter number: ");
    scanf("%d", &number);
 
    printf("Count of even digits in number %d: %u\n", number, count_even_digits(number));
 
    return 0;
}
 
size_t count_even_digits(int number)
{
    return !number ? 0 : !(number & 1) + count_even_digits(number / 10);
}

@Do6oDyH · 18.04.2011, 15:33 **[ТС]**

Спасибо большое. А вы уверены что тут всё правильно:

C

1	return !number ? 0 : !(number & 1) + count_even_digits(number / 10);

?

silent_1991 · 18.04.2011, 15:36

Do6oDyH, а вы нет? Чем вызвана неуверенность?

@Do6oDyH · 18.04.2011, 15:40 **[ТС]**

C

1	number ? 0

Что это значит?

silent_1991 · 18.04.2011, 15:48

Объясняю посимвольно:
?: - тернарный оператор. Если написано exp1 ? exp2 : exp3, это означает, что если exp1 истинно, то результатом операции будет exp2, в ином же случае exp3.
В данном случае: !number - проверка, не нулевое ли число. Если так - то достигнута база рекурсии, результатом будет 0. Если нет, то надо к итоговой сумме (которая получается в результате рекурсивных вызовов count_even_digits) прибавить 0 или 1, в зависимости от того, является ли очередная просматриваемая цифра числа (в данном случае - последняя) чётной или нечётной. number & 1 - проверка на чётность (младший разряд нечётного числа 1, чётного 0). Поскольку младший разряд последней цифры числа совпадает с младшим разрядом всего числа, нет смысла вычленять последнюю цифру через остаток от деления на 10, можно сразу проверить всё число. Так вот, если число у нас чётное, то мы к итоговой сумме (которая, повторюсь, получается неявно в последовательных рекурсивных вызовах) должны прибавить 1, иначе 0 (результат, инверсный результат проверки на чётность), а затем рекурсивно вызвать нашу функцию, но для числа без последней цифры (которую мы только что проверили и включили в результат).
В итоге результат можно расписать в виде суммы нулей и единиц, общее количество слагаемых равно количеству цифр числа, и на каждой позиции, где в числе стоит нечётная цифра, в сумме будет стоять 0, а где чётная - 1. Т.е. примерно так

Код

1   2   4   3   5   6   2   7
0 + 1 + 1 + 0 + 0 + 1 + 1 + 0

@Do6oDyH · 18.04.2011, 15:49 **[ТС]**

А можно как-то по другому?

silent_1991 · 18.04.2011, 15:52

Эхх... Хотелось как лучше... Примитивизм в действии)))

C

size_t count_even_digits(int number)
{
    int term = 0;
 
    if (number == 0)
        return 0;
 
    if (number % 2 == 0)
        term = 1;
 
    return term + count_even_digits(number / 10);
}

@Do6oDyH · 18.04.2011, 15:54 **[ТС]**

Спасибо

Блоги программистов
Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .	Полезные поделки на Arduino, которые можно сделать самому raxper 06.01.2025 Arduino как платформа для творчества Arduino представляет собой удивительную платформу для технического творчества, которая открывает безграничные возможности для создания уникальных проектов. Эта. . .	Подборка решений задач на Python IT_Exp 06.01.2025 Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .	С чего начать программировать микроконтроллеры raxper 06.01.2025 Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .
Из чего собрать игровой компьютер inter-admin 06.01.2025 Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .	Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного сумматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки). Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .	Руководство по созданию бота для Телеграм на Python IT_Exp 04.01.2025 Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .

@Do6oDyH 0 / 0 / 0 Регистрация: 25.10.2010 Сообщений: 71
		1
	Рекурсия: подсчет количества четных цифр числа (на С) 18.04.2011, 14:43. Показов 8742. Ответов 8 Метки нет (Все метки) Написать рекурсивную функцию считывающую количество четных цифр числа. Плохо понял рекурсию объясните на этом примере пожалуйста. 0

silent_1991 5057 / 3117 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.04.2011, 15:36	4
	Do6oDyH, а вы нет? Чем вызвана неуверенность? 0

silent_1991 5057 / 3117 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.04.2011, 15:48	6
	Объясняю посимвольно: ?: - тернарный оператор. Если написано exp1 ? exp2 : exp3, это означает, что если exp1 истинно, то результатом операции будет exp2, в ином же случае exp3. В данном случае: !number - проверка, не нулевое ли число. Если так - то достигнута база рекурсии, результатом будет 0. Если нет, то надо к итоговой сумме (которая получается в результате рекурсивных вызовов count_even_digits) прибавить 0 или 1, в зависимости от того, является ли очередная просматриваемая цифра числа (в данном случае - последняя) чётной или нечётной. number & 1 - проверка на чётность (младший разряд нечётного числа 1, чётного 0). Поскольку младший разряд последней цифры числа совпадает с младшим разрядом всего числа, нет смысла вычленять последнюю цифру через остаток от деления на 10, можно сразу проверить всё число. Так вот, если число у нас чётное, то мы к итоговой сумме (которая, повторюсь, получается неявно в последовательных рекурсивных вызовах) должны прибавить 1, иначе 0 (результат, инверсный результат проверки на чётность), а затем рекурсивно вызвать нашу функцию, но для числа без последней цифры (которую мы только что проверили и включили в результат). В итоге результат можно расписать в виде суммы нулей и единиц, общее количество слагаемых равно количеству цифр числа, и на каждой позиции, где в числе стоит нечётная цифра, в сумме будет стоять 0, а где чётная - 1. Т.е. примерно так Код 1 2 4 3 5 6 2 7 0 + 1 + 1 + 0 + 0 + 1 + 1 + 0 0

@Do6oDyH 0 / 0 / 0 Регистрация: 25.10.2010 Сообщений: 71
	18.04.2011, 15:49 [ТС]	7
	А можно как-то по другому? 0

@Do6oDyH 0 / 0 / 0 Регистрация: 25.10.2010 Сообщений: 71
	18.04.2011, 15:54 [ТС]	9
	Спасибо 0