1

我刚开始学习用 Java 教授的数据结构和算法。到目前为止，我一生中只学过 C++，所以我对使用 java 还是很陌生。

无论如何，我有一个家庭作业问题，我有点坚持：

编写一个递归方法，返回 N 的二进制表示中 1 的数量。如果 N 为奇数，则使用它等于 N/2 + 1 表示中 1 的数量这一事实。

现在我不确定该怎么做。我已经设置了一个函数，它接受一个整数并将其转换为二进制并将其存储在一个字符串中，但其余的我有点迷失了。

如果我能得到一些指导，那真的很有帮助。

这是我到目前为止所拥有的：

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());
  }
}

谢谢

4

4 回答 4

11

这不是一个很难解决的问题。你需要做的是停止编写代码，首先在纸上解决问题。然后将您的算法转换为代码。

于 2009-01-25T19:06:07.360 回答
5

第一步：想！

很难编写返回类型为 void 的递归方法。

于 2009-01-30T16:02:20.123 回答
4

问题是关于做算术，所以将值保留为 int 而不是转换为字符串。

然后有两个事实（对于非负数）：

  • 如果 N 是奇数，则 1 的个数与 N/2 中的相同，再加上一个余数；
  • 如果 N 是偶数，则个数与 N/2 中的相同。

010101 的 bitCount 是 010101/2 = 01010 的 bitCount 加上 010100 的 1 bitCount 是 010100/2 = 01010 的 bitCount

冲洗并重复直到完成（感应）。

只是不要看 Integer.bitCount 的来源。

于 2009-01-25T19:38:31.553 回答
1

首先，将问题简化为最简单的情况......

于 2009-01-25T19:36:07.657 回答