質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.48%

ピポット要素の特性 `7n/10`になることはあるのか

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 403

score 95

実現したいこと

中央値の中央値のアルゴリズムを作ってみました。
n個のリストについて考えます。
ここで再帰関数により選んだピポット要素より小さい値が7n/10ちょうどのときを探しています。
そのようになる値が出てくるようにリストとその要素数をランダムに作成しました。そしてそれを何回もシュミレーションするプログラムを作りました。しかし、ぴったり7n/10のとなるときは一度もありませんでした。
最大でも(7n/10)-1でした。
ぴったり7n/10となることはないのでしょうか。それかプログラムが間違っているのでしょうか。

コード

#選択アルゴリズムk番目

import math
import random
def selection(a,k,num):
    #print("input:",a,"k =",k)
    n=len(a)
    small=[]
    smallb=[]
    pilist=[]
    def pivot(a,k):
        if n>=5:
            #先頭から5つずつに分けていく
            for i in range(0,n,5): #[0]から[n]まで5こずつ
                if i+4<n: #nが5の倍数ではない場合、最後は廃棄
                    start=i #分けた配列の最初の添え字
                    end=i+5 #分けた配列の最後の添え字
                    #print("start=",start,"end=",end)

                    small=a[start:end] #小配列を作る
                    smallb=sorted(small) #ソートした小配列
                    #print("smallb=",smallb)
                    #print("smallb[2]=",smallb[2])
                    pilist.append(smallb[2]) #ピポット要素の配列
                    small.clear()
                    smallb.clear()

            #ピポット要素の配列でさらに中央値を求める(再帰)
            k=len(pilist)/2.0
            pip=selection(pilist,math.ceil(k),num)
            #print("return:",pip)
        else:
            k=n/2.0
            k=math.ceil(k)
            pip=a[k]
            #print("returnpip:",pip)
        return pip
    n=len(a) #aのデータ数
    L=[]
    R=[]
    if n<5:
        b=sorted(a)
        #print("k=",k)
        #print("return:",b[k-1])
        return b[k-1]
    else:
        pi=pivot(a,k) #ピポット要素
        #分割する
        for i in range(n):
            if a[i]<pi:
                L.append(a[i])
            elif a[i]>pi:
                R.append(a[i])
        nL=len(L) #Lのデータ数
        nR=len(R) #Rのデータ数
        numi=(7*num)/10
        numi=math.floor(numi)
        #print("numi=",numi)
        if (numi-1)<=nL:
            print("num=",num)
            print("numi=",numi)
            print("☆☆☆nL=",nL)
            print("ピポット要素:",pi)
        #print("L=",L)

        #k番目を探す
        if k<=nL:
            ans=selection(L,k,num)
        elif nL==k-1:
            #print("return:",pi)
            return pi #ピポット要素がk番目
        else:
            #print("②")
            ans=selection(R,k-nL-1,num)
        #print("return:",ans)
        return ans

# 重複なし
def rand_ints_nodup(a, b, k):
  ns = []
  while len(ns) < k:
    n = random.randint(a, b)
    if not n in ns:
      ns.append(n)
  return ns

a=[] #リスト
#リストに入力していく
for i in range(1000):
    num=random.randint(20,50) #リスト数
    #print("num=",num)
    a=rand_ints_nodup(0,100,num) #リストの中身
    print("a=",a)
    k=random.randint(1,num)
    print("answer:",selection(a,k,num))
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+1

以下の箇所で、pilistの長さが偶数の時、常に中央2つの小さい側をpivotに採用しているので、
pivotより小さい値の数が少なくなる方に偏るのでしょう。

            #ピポット要素の配列でさらに中央値を求める(再帰)
            k=len(pilist)/2.0
            pip=selection(pilist,math.ceil(k),num)


偶数の時、常に中央2つの大きい側をpivotに採用するようにすれば、
長さが10の倍数のときにぴったり7n/10になる可能性が出てきます。

            #ピポット要素の配列でさらに中央値を求める(再帰)
            k=(len(pilist)+1)/2.0
            pip=selection(pilist,math.ceil(k),num)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/12/07 22:26

    アドバイスありがとうございます。おかげで求めていた値が出てきました!!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る