－プログラミング－ 佐賀商業高等学校 シンデレラを探せ！ シンデレラが忘れていった ガラスの靴 この靴に合う足のサイズは、 線形探索で、 この サイズの 人 探してみよう。 ×× × × × 線形探索は、順番に探して いく方法なので、候補者が多 くなると、探索にかなり時間 がかかる可能性がある。 ○ × × シンデレラ候補の足 この人が シンデレラ シンデレラを探せ！ シンデレラが忘れていった ガラスの靴 この靴に合う足のサイズは、 二分探索で探してみよう。 その前に、 小さい順に並べー！！ シンデレラ候補の足 シンデレラを探せ！ シンデレラが脱ぎ忘れていった ガラスの靴 この靴に合う足のサイズは、 二分探索で探してみよう。 真ん中の人と比べると、 小さい順に並べー！！ 真ん中の人が 大きいということは × まず、真ん中の人を探す １．当然、真ん中の人はシンデレラではない。 ２．真ん中の人より大きい人たちも シンデレラではない。 一気に候補者が減った！！ シンデレラを探せ！ シンデレラが脱ぎ忘れていった ガラスの靴 この靴に合う足のサイズは、 二分探索で探してみよう。 真ん中の人と比べると、 真ん中の人が 小さいということは ×× × 残った候補者から、真ん中の人を探す １．当然、真ん中の人はシンデレラではない。 ２．真ん中の人より小さい人たちも シンデレラではない。 シンデレラを探せ！ シンデレラが脱ぎ忘れていった ガラスの靴 この靴に合う足のサイズは、 二分探索で探してみよう。 真ん中の人と比べると、 この人が シンデレラ ×× × 残った候補者から、真ん中の人を探す 二分探索は、候補者を半分 ずつ一気に減らすことができ るので、高速な探索ができる。 ただし、並べ替えが行われて いるのことが前提。 二分探索 入出力例 （例題）商品コードを入力し、そのコードに対応する商品名を出力する プログラムを作成せよ。 ＜処理条件＞ １．商品コードを画面より入力し、ICOに保存する。 025 055 030 エラー 999（終了） ２．商品コードはテーブルＣＯＤＥに、商品名はテーブルＭＥＩに あらかじめ記憶されている。 ３．テーブルは商品コードの昇順に並んでいる。 ４．９９９が入力されたときに処理を終了する。 ５．テーブルにない商品コードが入力された場合は画面に"エラー” と表示する。 MEI ﾃﾚﾋﾞ ﾋﾞﾃﾞｵ ｶﾒﾗ ｴｱｺﾝ ﾊﾟｿｺﾝ ｸﾘｰﾅｰ ﾌﾟﾘﾝﾀ ﾚﾝｼﾞ PSX ｶﾂﾄﾞﾝ (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 010 015 025 040 050 055 070 100 11 125 (1) (2) (3) (4) (5) (6) (7) (8) CODE (9) (10) ｶﾒﾗ ｸﾘｰﾅｰ 二分探索 はじめ （例題）商品コードを入力し、そのコードに対応する商品名を出力する プログラムを作成せよ。 ICO ＜処理条件＞ ループ１ １．商品コードを画面より入力し、ICOに保存する。 ICO = 999 ２．商品コードはテーブルＣＯＤＥに、商品名はテーブルＭＥＩに あらかじめ記憶されている。 ３．テーブルは商品コードの昇順に並んでいる。 0 → SW 下限の初期 値はいつも０ ５．テーブルにない商品コードが入力された場合は画面に"エラー” と表示する。 上限の初期値は 印字 テーブルの数＋１ ４．９９９が入力されたときに処理を終了する。 ﾋﾞﾃﾞｵ ｶﾒﾗ ｴｱｺﾝ ﾊﾟｿｺﾝ ｸﾘｰﾅｰ ﾌﾟﾘﾝﾀ ﾚﾝｼﾞ PSX ｶﾂﾄﾞﾝ (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (KA+JO)/2 →TYU ICO=CODE(TYU) YES MEI(TYU) YES NO 1 → SW TYU→KA 11 → JO YES NO “エラー” の場合 < CODE 下限と上限を足 して２で割り、 真ん中を指定 NO ICO 025 10 SW = 1 TYU→JO MEI ﾃﾚﾋﾞ ループ２ ICO>CODE(TYU) 0 → KA ＳＷは探索 が終わったこ SWとを知らせる 役割 1 → SW 010 015 025 040 050 055 070 100 110 125 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) ↑ ↑ ↑ KA TYU JO ループ２ ICO 候補 ループ１ 候補 ＫＡの右隣からＪＯの左隣までが候補 ↑ おわり JO ↑ ↑ KA TYU 二分探索 はじめ （例題）商品コードを入力し、そのコードに対応する商品名を出力する プログラムを作成せよ。 ループ２ SW SW = 1 10 ICO ＜処理条件＞ ループ１ １．商品コードを画面より入力し、ICOに保存する。 ICO = 999 ２．商品コードはテーブルＣＯＤＥに、商品名はテーブルＭＥＩにあ らかじめ記憶されている。 ３．テーブルは商品コードの昇順に並んでいる。 (KA+JO)/2 →TYU ICO=CODE(TYU) NO 0 → SW ４．９９９が入力されたときに処理を終了する。 ICO>CODE(TYU) ５．テーブルにない商品コードが入力された場合は画面に"エラー” と表示する。 ﾋﾞﾃﾞｵ ｶﾒﾗ ｴｱｺﾝ ﾊﾟｿｺﾝ ｸﾘｰﾅｰ ﾌﾟﾘﾝﾀ ﾚﾝｼﾞ PSX ｶﾂﾄﾞﾝ (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 030 エラー 例 の場合 < CODE 010 015 025 040 050 055 070 100 110 125 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) JO = KA+1 ＫＡとＪＯが隣合う という意味。 候補が無くなるので、 該当コードは存在し なかった。 ↑ ↑ ↑ KA TYU JO YES “エラー” 1 → SW ループ２ ICO 候補が 無くなった！！ TYU→KA 11 → JO NO ICO MEI(TYU) 1 → SW TYU→JO ﾃﾚﾋﾞ YES NO 0 → KA MEI YES ループ１ おわり 二分探索 はじめ （例題）商品コードを入力し、そのコードに対応する商品名を出力する プログラムを作成せよ。 ICO ＜処理条件＞ SW ループ２ SW = 1 １．商品コードを画面より入力し、ICOに保存する。 ２．商品コードはテーブルＣＯＤＥに、商品名はテーブルＭＥＩに あらかじめ記憶されている。 ループ１ ICO = 999 ３．テーブルは商品コードの昇順に並んでいる。 ４．９９９が入力されたときに処理を終了する。 0 → SW ５．テーブルにない商品コードが入力された場合は画面に"エラー” と表示する。 ICO=CODE( YES ) YES NO ICO>CODE( MEI ) NO ﾃﾚﾋﾞ ﾋﾞﾃﾞｵ ｶﾒﾗ ｴｱｺﾝ ﾊﾟｿｺﾝ ｸﾘｰﾅｰ ﾌﾟﾘﾝﾀ ﾚﾝｼﾞ PSX ｶﾂﾄﾞﾝ (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 1 → SW ICO YES の場合 NO CODE 010 015 025 040 050 055 070 100 110 125 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) “エラー” 1 → SW ループ２ ICO の場合 CODE ICO 010 015 025 040 050 055 070 100 110 125 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) ループ１ おわり ↑ ↑ ↑ JO KA TYU
© Copyright 2024 ExpyDoc
