Определить максимальную цифру в 16-ричной записи числа n. Нужна не программа, а сама рекурсивная функция. В универе выделили этому всего лишь одно занятие. Помогите, будьте добры.

задан 20 Июн '19 17:33

10|600 символов нужно символов осталось
0

Для начала см. близкую по содержанию задачу здесь. Там дан ряд ссылок.

Здесь идея такая же. Мы берём число x, и делим его с остатком на основание системы счисления, равное g. В данном примере g=16, но можно для иллюстрации рассмотреть случай g=10. От числа мы переходим к следующему, беря неполное частное от деления на g. Это приводит к списыванию последней цифры числа, и в итоге получается 0. Например, для 1234 мы получим далее 123, 12, 1, 0, ... .

То есть мы по рекурсии строим функцию f(x,y), полагая

f(x,0)=x

f(x,y+1)=quo(f(x,y),16)

и получаем рекурсивную функцию. От каждого получившегося числа f(x,y) мы берём остаток от деления на g=16, получая ф(x,y)=rem(f(x,y),16). Это рекурсивная функция, которая выдаёт цифры числа x в заданной системе счисления в порядке справа налево. В конце получаются нули.

Теперь нам надо выявить максимум чисел ф(x,0), ф(x,1), ф(x,2), ... . Введём функцию m(x,y) которая равна максимуму среди первых y чисел указанного списка. Она задаётся по рекурсии:

m(x,0)=0 (начальное присвоение) и далее

m(x,y+1)=max(m(x,y),ф(x,y+1))

То есть мы пошагово берём максимум среди "текущего" значения и очередного числа последовательности. Про функцию max двух аргументов уже известно, что она рекурсивна (см. Мендельсон).

Осталось положить m(x,x), применяя оператор подстановки. Это даст максимальную цифру, так как на шаге x последовательность точно стабилизируется.

ссылка

отвечен 20 Июн '19 19:39

Благодарю вас, сейчас буду разбираться.

(20 Июн '19 19:56) Kar_Angels
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×194
×32

задан
20 Июн '19 17:33

показан
352 раза

обновлен
20 Июн '19 19:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru