4

JasonHickeyのObjectiveCaml入門を学んでいます。

このような演習があります：

演習4.3次の換字式暗号に基づく暗号システムがあり、各プレーンレターは次の表に従って暗号化されているとします。

Plain     | A B C D
--------------------
Encrypted | C A D B

たとえば、文字列BADはとして暗号化されACBます。

check平文文字列s1と暗号文文字列s2が与えられた場合に、s2がs1の暗号文である場合にのみ返される関数を記述します。s 1がプレーンテキスト文字列でない場合、関数は例外を発生させる必要があります。8ページの文字列操作を参照することをお勧めします。アルファベットが大きくなるにつれて、コードはどのようにスケーリングされますか？[強調追加]true

基本的に、私はmight-be-stupid-naiveこの演習の方法で2つの関数を作成しました。

まず、自分の解決策についてアドバイスを求めたいと思います。

次に、演習で強調したように、スケーリングされたソリューションのヒントを求めたいと思います。

ifelseを使用する

let check_cipher_1 s1 s2 = 
    let len1 = String.length s1 in
        let len2 = String.length s2 in              
            if len1 = len2 then
                    let rec check pos =
                        if pos = -1 then
                            true
                        else
                            let sub1 = s1.[pos] in
                                let sub2 = s2.[pos] in
                                    match sub1 with
                                        | 'A' -> (match sub2 with
                                                    |'C' -> check (pos-1)
                                                    | _ -> false)
                                        | 'B' -> (match sub2 with
                                                    |'A' -> check (pos-1)
                                                    | _ -> false)
                                        | 'C' -> (match sub2 with
                                                    |'D' -> check (pos-1)
                                                    | _ -> false)
                                        | 'D' -> (match sub2 with
                                                    |'B' -> check (pos-1)
                                                    | _ -> false)
                                        | _ -> false;
                                            in
                                                check (len1-1)
            else
                false

どこでも純粋な一致を使用する

let check_cipher_2 s1 s2 = 
    let len1 = String.length s1 in
        let len2 = String.length s2 in
            match () with
                | () when len1 = len2 -> 
                        let rec check pos =
                            match pos with
                                | -1 -> true
                                | _ -> 
                                    let sub1 = s1.[pos] in
                                        let sub2 = s2.[pos] in
                                            (*http://stackoverflow.com/questions/257605/ocaml-match-expression-inside-another-one*)
                                            match sub1 with
                                                | 'A' -> (match sub2 with
                                                            |'C' -> check (pos-1)
                                                            | _ -> false)
                                                | 'B' -> (match sub2 with
                                                            |'A' -> check (pos-1)
                                                            | _ -> false)
                                                | 'C' -> (match sub2 with
                                                            |'D' -> check (pos-1)
                                                            | _ -> false)
                                                | 'D' -> (match sub2 with
                                                            |'B' -> check (pos-1)
                                                            | _ -> false)
                                                | _ -> false
                                                    in
                                                        check (len1-1)
                | () -> false

Ok。上記の2つのソリューションは似ています。

ここhttp://www.quora.com/OCaml/What-is-the-syntax-for-nested-IF-statements-in-OCamlで、これは好ましくないと言う人もいるので、私はこれら2つを作成しましたif else。

not-that-simpleこれは、私が人生で関数を書いたのは本質的に初めてです。だから私はここでの提案に本当に飢えています。

たとえば、

  • これらのソリューションをどのように改善できますか？
  • 私はよりも好むべきですmatchかif else？
  • 私はまたは正しく設計していrecますuse the recか？
  • それがin check (len1-1)正しければ？

スケーリングする

演習では尋ねHow does your code scale as the alphabet gets larger?ます。今のところ、私には本当に手がかりがありません。Javaでは、を持っていると言いますmap。次に、の各文字について、対応する文字s1を探しs2、それがマップ内の値であるかどうかを確認します。

これに関する提案はありますか？

4

3 に答える 3

5

簡単な解決策は次のとおりです。

tr = 関数とする
  | | 'A' -> 'C'
  | | 'B' -> 'A'
  | | 'C' -> 'D'
  | | 'D' -> 'B'
  | | _ -> 「平文ではない」で失敗

let check ~tr s1 s2 = (String.map tr s1) = s2

チェック ~tr "BAD" "ACD"

tr で構成することにより、さらに文字を追加できます。いえ

let comp c1 c2 x = try (c1 x) with _ -> (c2 x)
let tr2 = comp tr (関数 | 'X' -> 'Y')
于 2013-01-15T18:02:43.590 に答える
3
  • これらのソリューションを改善するにはどうすればよいですか?

インデントを誤用すると、プログラムが読みにくくなります。不要なタブを削除checkし、読みやすくするために外側のスコープに移動します。

let check_cipher_1 s1 s2 = 
    let rec check pos =
        if pos = -1 then
            true
        else
            let sub1 = s1.[pos] in
            let sub2 = s2.[pos] in
            match sub1 with
            | 'A' -> (match sub2 with
                      |'C' -> check (pos-1)
                      | _ -> false)
            | 'B' -> (match sub2 with
                      |'A' -> check (pos-1)
                      | _ -> false)
            | 'C' -> (match sub2 with
                      |'D' -> check (pos-1)
                      | _ -> false)
            | 'D' -> (match sub2 with
                      |'B' -> check (pos-1)
                      | _ -> false)
            | _ -> false in
    let len1 = String.length s1 in
    let len2 = String.length s2 in              
    if len1 = len2 then
            check (len1-1)
    else false
  • それ以外の場合は、一致を優先する必要がありますか?

場合によります。2 番目の関数 ( match () with | () when len1 = len2)で示したように、パターン マッチングが表面的なものである場合、単純な構造と比較して価値はありませんif/else。値に対してパターン マッチif/elseを行う場合は、高度な構造を使用する場合よりも優れており、短縮される可能性があります。たとえば、タプルを照合することで関数を短縮できます。

let check_cipher_1 s1 s2 =  
    let rec check pos =
        if pos = -1 then
           true
        else
            match s1.[pos], s2.[pos] with
            | 'A', 'C' | 'B', 'A' 
            | 'C', 'D' | 'D', 'B' -> check (pos-1)
            | _ -> false in
    let len1 = String.length s1 in
    let len2 = String.length s2 in 
    len1 = len2 && check (len1 - 1)

ここでも Or パターンを使用して、同じ出力アクションを持つパターンをグループ化し、不要なif/elseブロックを で置き換え&&ます。

  • rec を設計していますか、または rec を正しく使用していますか?
  • それがチェックされている場合 (len1-1) 正しいですか?

あなたの機能は良さそうです。OCaml トップレベルでいくつかの入力を使ってテストするより良い方法はありません。

スケーリングする

パターンの数は、アルファベットのサイズに比例して増加します。それはかなりいいIMOです。

于 2013-01-15T17:59:43.943 に答える
2

最も簡単な解決策は、テキストを暗号化して結果を比較することです。

let cipher_char = function
   | 'A' -> 'C'
   | 'B' -> 'A'
   | 'C' -> 'D'
   | 'D' -> 'B'
   | _ -> failwith "cipher_char"
let cipher = String.map cipher_char
let check_cipher s1 s2 = (cipher s1 = s2)

このcipher_char関数は、アルファベットのサイズに比例してスケーリングします。それをもう少しコンパクトで一般的なものにするために、ある形式のルックアップテーブルを使用することができます。

(* Assume that only letters are needed *)
let cipher_mapping = "CADB"
let cipher_char c =
   try cipher_mapping.[Char.code c - Char.code 'A']
   with Invalid_argument _ -> failwith "cipher_char"
于 2013-01-15T18:21:40.070 に答える