Как мне понять этот сложный алгоритм рекурсии?

Question

Я только что начал структуры данных и алгоритмы, которые преподаются на Java. До сих пор я только изучал C ++ в своей жизни, поэтому я все еще ОЧЕНЬ новичок в использовании Java.

В любом случае, у меня проблема с домашней работой, на которой я немного застрял:

Напишите рекурсивный метод, который возвращает число 1 в двоичном представлении N. Используйте тот факт, что оно равно числу 1 в представлении N / 2 + 1, если N нечетное.

Теперь я не уверен, как именно это сделать. У меня уже есть настроенная функция, которая принимает целое число, преобразует его в двоичный файл и сохраняет в виде строки, но все остальное я как бы потерян.

Если бы я мог получить какое-то руководство, это действительно помогло бы.

Это то, что я имею до сих пор:

import java.io.*;
public class Homework1Code {
  static void prtbinary(String Molly, int size){
    if(size <=0){
      return;
    }
  }

  public static void main(String[] args) {
    int i = 38;
    String binstr = Integer.toBinaryString(i);
    System.out.println("The Original Decimal Number is: " + binstr);
    prtbinary(binstr, binstr.length());
  }
}

Спасибо

Answer 1

Это не сложная проблема для решения. Что вам нужно сделать, это прекратить писать код и сначала решить проблему на бумаге. Затем преобразуйте свой алгоритм в код.

Answer 2

Шаг первый: думай!

Очень трудно написать рекурсивный метод с возвращаемым типом void.

Answer 3

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

Тогда есть два факта (для неотрицательных чисел):

• если N нечетно, то число единиц такое же, как в N / 2 плюс один остаток;
• если N четное, то число единиц такое же, как в N / 2.

bitCount из 010101 является bitCount из 010101/2 = 01010 плюс 1 bitCount 010100 является bitCount 010100/2 = 01010

Промыть и повторить до конца (индукция).

Только не смотрите на источник в Integer.bitCount.

Answer 4

сначала уменьшите проблему до самого простого случая ...