1

再帰関数を使用してバイナリ配列をプロモートするにはどうすればよいですか。この関数は、2進配列Vを受け取り、Vで表される数の値を、同じ1の数で次の数に増やします。操作が実行できる場合、関数はtrueを返します（java）

例：

v = {0,0,0,1,1,0,0,1,1} => return true, v = {0,0,0,1,1,0,1,0,1}

私はこれを書きます：

public static boolean incrementSameOnes(int[] vec)  {
    boolean succ=false;
    int[] v=new int[vec.length-1];
    if(vec.length==1){
        return false;
    }
    if (vec[vec.length-1]==1 && vec[vec.length-2]==0)
    {
        vec[vec.length-2] = 1;
        vec[vec.length-1] = 0;
        System.out.print(Arrays.toString(vec));
        return true;
    }else {
        for(int j=0;j<vec.length-1;j++)
            v[j]=vec[j];
        succ=incrementSameOnes(v);  
        }
    return succ;
}
4

1 に答える 1

0

私の理解が正しければ、バイナリ表現で設定されたビット数が同じで、次に高い整数を見つけたいと考えていますよね？もしそうなら、私は提案します：

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] x = { 1, 1, 1, 0, 1, 1, 0 };
        System.out.println("original: " + Arrays.toString(x));
        if (promote(x)) System.out.println("promoted: " + Arrays.toString(x));
        else System.out.println("not promotable");
    }

    private static boolean promote(int[] x) {
        // convert to integer value
        int value = 0;
        for (int i = 0; i < x.length; i++) {
            value += x[x.length - 1 - i] * (1 << i);
        }
        int newValue = value + 1, maxValue = 1 << x.length;
        int nBits = getNumberOfSetBits(value);

        // increase value until same amount of set bits found
        while (newValue < maxValue && getNumberOfSetBits(newValue) != nBits)
            newValue++;

        // convert back to array
        if (newValue < maxValue) {
            for (int i = 0; i < x.length; i++) {
                x[x.length - 1 - i] = (newValue & (1 << i)) >> i;
            }
            return true;
        } else {
            return false;
        }
    }

    // kung fu magic to get number of set bits in an int
    // see http://stackoverflow.com/a/109025/1137043
    private static int getNumberOfSetBits(int i) {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }
}

出力：

original: [1, 1, 1, 0, 1, 1, 0]
promoted: [1, 1, 1, 1, 0, 0, 1]

編集:あなたの例のような2D配列の場合、intへの変換と配列形式への変換は少し異なりますが、同じアプローチをお勧めします.

于 2012-12-05T09:57:32.727 に答える