抽出アルゴリズムの考案

閲覧数2,823
ダウンロード数2
履歴確認

    • ページ数 : 8ページ
    • 会員550円 | 非会員660円

    資料紹介

    n個の整数を要素とする1次元配列Aの中から、要素の値の小さな順にk個までの要素を抽出したい。これを実現するための効率の良いアルゴリズムを考案せよ。ただし、nは比較的大きな数であり、またkはnに比べて非常に小さいものとする。
    (ヒント)k<<nなので、与えられたn個のデータを全て昇順に整列させてから必要なk個のデータを抽出するのでは効率が悪い。したがって、全てのデータを整列させずに必要なk個のデータを得る方法を考えると良い。
    考案したアルゴリズム
    (1)n個の整数を要素とする1次元配列Aを半順順序木としたヒープBに組み直す。
    (2)ヒープBをヒープソートの手順にて降順にソートを行うが、小さい数値からk個のみ確定した時点でヒープソートを中止する。この場合、ヒープBにおいて、B[n]〜B[n - k + 1]の要素が、小さな順のk個の要素となる。
    考案したアルゴリズムの例
    例を示すため、配列の要素数nは、9とし、抽出する要素の小さな値の個数kは、3とする。
    (1)下記のような配列Aを半順序木へ組みなおし、ヒープBとする。
    添字 1 2 3 4 5 6 7 8 9
    要素 3 11 15 12 5 7 14 10 9

    ?添字1の要素3をヒープBに追加する

    資料の原本内容 ( この資料を購入すると、テキストデータがみえます。 )

    抽出アルゴリズム レポート
    n個の整数を要素とする1次元配列Aの中から、要素の値の小さな順にk個までの要素を抽出したい。これを実現するための効率の良いアルゴリズムを考案せよ。ただし、nは比較的大きな数であり、またkはnに比べて非常に小さいものとする。
    (ヒント)k<<nなので、与えられたn個のデータを全て昇順に整列させてから必要なk個のデータを抽出するのでは効率が悪い。したがって、全てのデータを整列させずに必要なk個のデータを得る方法を考えると良い。
    考案したアルゴリズム
    n個の整数を要素とする1次元配列Aを半順順序木としたヒープBに組み直す。
    ヒープBをヒープソートの手順にて降順にソートを行うが、小さい数値からk個のみ確定した時点でヒープソートを中止する。この場合、ヒープBにおいて、B[n]~B[n - k + 1]の要素が、小さな順のk個の要素となる。
    考案したアルゴリズムの例
    例を示すため、配列の要素数nは、9とし、抽出する要素の小さな値の個数kは、3とする。
    下記のような配列Aを半順序木へ組みなおし、ヒープBとする。
    添字123456789要素31115125...

    コメント0件

    コメント追加

    コメントを書込むには会員登録するか、すでに会員の方はログインしてください。