Подсчитать количество нулей в двоичной записи n. Например 46 ->101110? Помогите пожалуйста

задан 24 Май '19 12:03

Не программу, а рекурсивную функцию для вычисления, тема относящаяся к суперпозиции, проекции и подобным

(24 Май '19 18:52) MrGoji
10|600 символов нужно символов осталось
0

Рассмотрим функцию f(x,y), заданную по рекурсии:

f(x,0)=x

f(x,y+1)=h(f(x,y))

где h(z)=z/2, если z чётно и h(z)=z, если z нечётно. Функция h(z) рекурсивна, так как выражается через функции quo(a,b) и rem(a,b) целочисленного частного и остатка, которые должны были строиться ранее. А именно, мы берём здесь неполное частное от деления z на 2 или 1 в зависимости от чётности, то есть это quo(z,2-rem(z,2)). Разность подразумевается ограниченной.

Значения функции f(x,y) при y=0,1,2,... можно наглядно представить в виде последовательности. Например, при x=48 мы имеем 48, 24, 12, 6, 3, 3, ... . Очевидно, что при x>=1 мы примерно за log_2(x) шагов получим стабилизацию. В частности, после члена с номером x она уже точно наступить

От каждого из чисел списка f(x,y) при 0<=y<=x, нам нужна 1 в "копилку", если число списка чётно, и 0 если нечётно. Складывая эти величины, мы получим то, что хотим (число нулей на конце в двоичной записи). Легко видеть, что функция u(z)=1-rem(z,2) даёт 1 на чётном числе и 0 на нечётном. Поэтому достаточно просуммировать u(f(x,y)) в указанных выше пределах от 0 до x.

Здесь можно или сослаться на общий факт о том, что суммирование (примитивно) рекурсивных функций в (примитивно) рекурсивных пределах обладает этим же свойством, или непосредственно применить оператор рекурсии, полагая

F(x,0)=0

F(x,y+1)=F(x,y)+u(f(x,y))

Понятно, что F(x,y) будет суммой величин u(f(x,t)) по 0<=t < y, и теперь достаточно применить оператор подстановки, беря F(x,x+1).

Заметим, что мю-оператор тут не потребовался, то есть построенная функция примитивно-рекурсивна.

ссылка

отвечен 25 Май '19 0:45

Спасибо, буду разбираться)

(25 Май '19 12:11) MrGoji

Что бы я без вас делал)

(25 Май '19 12:12) MrGoji

Просто на эту тему выделили 1 занятие, а понятия не пришло(

(25 Май '19 12:14) MrGoji

@MrGoji: да, одного занятия на эту тему маловато. Я обычно в своём курсе уделяю много часов теме рекурсивных функций. К тому же, эта задача по уровню несколько сложнее "среднего".

Если что, эти вещи неплохо изложены в книге Мендельсона.

(25 Май '19 12:58) falcao

@MrGoji: я сейчас заметил, что привёл решение несколько не той задачи. Вместо количества нулей в двоичной записи, которое для 46 равно двум, я указал способ нахождения количества нулей на конце, то есть показатель степени 2 в каноническом разложении. Который для 46 равен единице. Но другая задача решается похожим способом. Сейчас спросили почти то же самое про количество единиц, и я обнаружил, что ответил несколько не на тот вопрос.

(20 Июн '19 17:09) falcao
10|600 символов нужно символов осталось
0

Я не очень понял, тебе что нужно? Написать программу?

Всё относительно просто берётся наибольшая степень двойки, которая меньше первоначального числа - в нашем случае 46

В нашем случае это 32. Вычитаем 32 из 46. Остаётся 14 Дальше действуем по такому алгориму

1) степень двойки делим на два. Если результат 1/2 - выходим из алгоритма - Конец

2) если получившаяся новая степень двойки меньше остатка (или равно) - вычитаем её из остатка и переходим к пункту 1)

3) если получившаяся новая степень двойки больше остатка - считаем, что у нас есть ещё один ноль. И переходим к пункту 1)

Например, разберём пример для 46

берём 32 и вычитаем из 46 - остаток 14 1) делим 32 на два - получается 16 2) 16 > 14. Пропускаем пункт 2 3) 16 > 14. Значит, у нас есть первый ноль. Переходим к 1) 1) делим 16 на два - получается 8 2) 8 < 14. Вычитаем 8 из 14. Остаток 6. Переходим к 1) 1) делим 8 на два - получается 4 2) 4 < 6. Вычитаем 4 из 6. Остаток 2. Переходим к 1) 1) делим 4 на два - получается 2 2) 2 = 2. Вычитаем 2 из 2. Остаток 0. Переходим к 1) 1) делим 2 на два - получается 1 2) 1 > 0. Пропускаем 3) 1 > 0. Имеем второй ноль. Переходим к 1. 1) Делим 1 на два - получается 1/2 - выходим из алгоритма Итого два нуля.

ссылка

отвечен 24 Май '19 12:29

Не программу, а рекурсивную функцию для вычисления, тема относящаяся к суперпозиции, проекции и подобным

(24 Май '19 16:25) MrGoji

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

(24 Май '19 17:19) w2kzx80

альтернативный вариант - что-то типа

function find_first_stepeni(find,stepeni)

{

if (stepeni2>find) return stepeni2;

return find_first_stepeni(stepeni*2);

}

function count_zero(ostatok, stepeni)

{

var s2= stepeni/2;

if (s2 == 0.5) return 0;

if (s2 <= ostatok) return count_zero(base-s2,s2)

return 1+count_zero(base, s2);

}

var first_stepeni=find_first_stepeni(46); var find_zero = count_zero(46, first_stepeni);

где в базовом вызове функции первое число всегда 0, второе - искомое число, а третье - всегда 1.

Думаю, это то, что тебе надо

(24 Май '19 17:39) w2kzx80

Проверим, как это работает на примере 46

1) find_first_stepeni(46) - очевидно, вернёт 64

2) count_zero(46, 64)

3) s2= 32;

4) s2<= 46 => return count_zero(46-32, 32)

5) count_zero(14, 32)

  6) s2= 16

  7) s2>14 => return 1+count_zero(14, 16)

  8) count_zero(14,16)

     9) s2=8

     10) s2<=14 => return count_zero(14-8,8)

     11) count_zero(6, 8)

        12) s2=4

        13) 4<=6 => return count_zero(6-4, 4)

        14) count_zero(2,4)
(24 Май '19 17:40) w2kzx80
           15) s2=2

           16) 2<=2 => return count_zero(2-2,2)

           17) count_zero(0,2)

              18) s2=1

              19) 1>0 => return 1+count_zero(0,1)

              20) count_zero(0,1)

                 21) s2=0.5 => return 0

              21) > 19 - return 1+0

           22) > 16 return 1

        23) > 13 return 1

     24) > 10 return 1

  25) > 7 return 1+1

26) >4 return 2

27) RESULT = 2

Вроде, правильно)

(24 Май '19 17:40) w2kzx80

Эх, не программу надо, сверху в правках данные более точные

(24 Май '19 23:53) MrGoji
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×194
×32

задан
24 Май '19 12:03

показан
632 раза

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

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

по почте:

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

по RSS:

Ответы

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

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