1

このヨセフス問題の実装のどこが不十分なのですか? ジョセフス問題に慣れていない人のために説明すると、目標は循環リンク リストから 3 つおきのエントリを 1 つだけになるまで削除することです。この例では、すべての「mth」値を削除しています。

(define (joseph lst)  
(let ((m (+ 1 (random (length lst)))))
(define (joseph-h i xlst mlst)
 (cond ((<= (length xlst) 1) xlst)
       ((null? (cdr mlst)) 
        (joseph-h i xlst xlst))
       ((= i m) 
        (joseph-h 1 (delete (car mlst) xlst) (cdr mlst)))
       (else 
        (joseph-h (+ i 1) xlst (cdr mlst)))))
 (joseph-h 0 lst lst)))

 (joseph (list 1 2 3 4 5 6 7))


 (define (delete v lst)
   (cond ((= v (car lst)) 
          (cdr lst))
         (else
          (cons (car lst) (delete v (cdr lst))))))

私はいつも、リストの最後の番号を答えにしています。私はこれが正しくないことを知っています。

4

2 に答える 2

2

リストを作成し、そこから要素を削除する (人を「殺す」) ことにより、アルゴリズムを文字通りに解釈しすぎています。より簡単な解決策は、算術演算を使用して問題をモデル化することです。これは、私自身の以前の回答から適応した可能な実装です。

(define (joseph n k)
  (let loop ([i   1]
             [acc 0])
    (if (> i n)
        (add1 acc)
        (loop (add1 i)
              (modulo (+ acc k) i)))))

たとえば、'(1 2 3 4 5 6 7)3 人に 1 人を殺した後、リスト内でどの位置が生き残っているかを確認するには、次のようにします。

(joseph 7 3)
=> 4

ウィキペディアは、この問題の可能な解決策に関する興味深い議論を提供しています。私の解決策は、末尾再帰に変換した後、示されている単純な python 関数を適応させます。

于 2013-12-05T16:24:15.070 に答える
1

私のブログでは 3 つの解決策を紹介しています。最もリテラルなバージョンは、 mのステップでn 個のアイテムのリストから削除し、リストを循環リストとして表します。

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus3 n m)
  (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))
    (cond ((= (car alive) (cadr alive))
            (reverse (cons (car alive) dead)))
          ((= k 1)
            (let ((dead (cons (cadr alive) dead)))
              (set-cdr! alive (cddr alive))
              (loop (- m 1) (cdr alive) dead)))

これは、削除された要素をリストから実際に削除し、aliveリストに配置することで削除を行いdeadます。range関数は私の標準プレリュードからのものです。0 から までの整数を返しますn-1。

(define (range first past . step)
  (let* ((xs '()) (f first) (p past)
         (s (cond ((pair? step) (car step))
                  ((< f p) 1) (else -1)))
         (le? (if (< 0 s) <= >=)))
    (do ((x f (+ x s))) ((le? p x) (reverse xs))
      (set! xs (cons x xs)))))

元のヨセフスの問題では、3 段階で 41 人の男性が死亡し、1 から数えて 31 人目の男性が生存者として残りました。

(josephus3 41 3) (2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30)

私のブログで、他の 2 つのバージョンもお楽しみいただけます。

于 2013-12-05T16:35:44.407 に答える