0

"---" のような入力を 000,001,010,011,100,101,110, および 111 に変換する関数を作成しようとしています。別の例は "1--" -> 100,101,110,111 です。これまでのコードは次のとおりですが、ソリューションの一部しか生成していません。

static void expandPLA(char[]plaRow){
        boolean sawDontCare=false;
        for(int x = 0; x< plaRow.length; x++){
            if(plaRow[x]=='-'){
                sawDontCare=true;
                plaRow[x]='0';
                expandPLA(plaRow);
                plaRow[x]='1';
                expandPLA(plaRow);
            }
        }
        if(!sawDontCare)
            arrayList.add(plaRow);    
    }

arrayList は出力値を保持します。誰が何が悪いのか分かりますか？

4

3 に答える 3

2

上記のような値のリストを出力する実装例を作成しました。もちろん、コンソールに出力する代わりに、好きなことを行うことができます。

import java.util.*;
import java.lang.*;

class Main {

    public static void expandPLA(char[] pla) {

        // How many don't cares are we handling
        int empties = 0;
        for (int i = 0; i < pla.length; i++) {
            if (pla[i] == '-') { empties++; }
        }

        // Now we know we're counting from 0 to 2^empties in binary
        for (int j = 0; j < Math.pow(2,empties); j++) {

            // For each value of j we're going to create a new string pattern
            // and fill in each don't care with the correct digit of j
            String pattern = String.copyValueOf(pla);
            String bin = Integer.toBinaryString(j);

            // Pad bin with zeros
            int pad = empties - bin.length();
            for (int z = 0; z < pad; z++) {
                bin = "0" + bin;
            }

            // For each empty spot we're going to replace a single '-' with
            // the next most significant digit
            for (int k = 0; k < empties; k++) {
                char digit = bin.charAt(k);
                pattern = pattern.replaceFirst("-", String.valueOf(digit));
            }

            // We're just going to print this out for now, but you can do
            // whatever it is you want at this point.
            System.out.println(pattern);

        }

    }

    public static void main (String[] args) throws java.lang.Exception {
        Main.expandPLA(new char [] { '1', '-', '-', '1', '-', '1', '-', '-' });
    }

}

注：上記の私のアルゴリズムは、大幅に強化される可能性があります。私は 2 進数に 0 を埋め込むのが面倒なので、文字列を置換するよりも、ドント ケア スペースに数字を入れるためのより良い方法がある可能性があります。これは、メモリと時間の効率が向上する可能性がある概念の証明であると考えてください。ただし、再帰よりも優れていると私は信じています。

于 2013-03-20T02:28:51.417 に答える
0

本当に再帰が必要な場合は、次のようなものが機能するはずです。

static final char[] digits = new char[]{'0','1'};

private void expandPLA(char[] plaRow, char[] value, int x) {
    if (x == plaRow.length) {
        arrayList.add(value);
        return;
    }
    if (plaRow[x] == '-') {
        for (char digit : digits) {
            value[x] = digit;
            expandPLA(plaRow, value, x + 1);
        }
    } else {
        value[x] = plaRow[x];
        expandPLA(plaRow, value, x + 1);
    }
}
于 2013-03-20T02:37:08.910 に答える
0

再帰的ですが、Java ではありません。

(define (expand-pla code)
  (define (cons-of x) (lambda (l) (cons x l)))
  (define cons-1 (cons-of #\1))
  (define cons-0 (cons-of #\0))

  (map list->string
       (let building ((codes  (string->list code)))
         (if (null? codes)
             (list '())
             (let ((rest (building (cdr codes))))
               (case (car codes)
                 ((#\0) (map cons-0 rest))
                 ((#\1) (map cons-1 rest))
                 ((#\-) (append (map cons-0 rest)
                                (map cons-1 rest)))))))))

もしかしたら、面白いと思うかもしれません。そして、それは動作します：

> (expand-pla "1--")
("100" "101" "110" "111")

これは末尾再帰バージョンです。

(define (expand-pla code)
  (define (cons-of x) (lambda (l) (cons x l)))
  (define cons-1 (cons-of #\1))
  (define cons-0 (cons-of #\0))
  (define (compose f g) (lambda (x) (f (g x))))

  (let building ((codes (string->list code)) (result (list '())))
    (if (null? codes)
        (map (compose list->string reverse) result)
        (building (cdr codes)
                  (case (car codes)
                    ((#\0) (map cons-0 result))
                    ((#\1) (map cons-1 result))
                    ((#\-) (append (map cons-0 result)
                                   (map cons-1 result))))))))
于 2013-03-20T02:45:21.287 に答える