HSPTV!掲示板

こんにちは。
プログラミングの世界では普通に行うことを、(Fizzbuzz問題に乗っかって)わざわざ問題にしました。

[問題]
任意の要素からなる昇順にならんだ集合から、特定の要素が何番目にあるかを最も効率的に調べるプログラムを作りなさい。
という問題です。

ルールは、次の通りです。
[ルール]
集合は、どんな形式のものでも任意の要素が入れば良い。
任意の要素は、すべて整数である。
任意の要素は、重複している要素があってもいい。
特定の要素が集合の中に見つからなかった場合は無かったということ示すメッセージを出力する。
特定の要素が複数ある場合、全て挙げる。

そのほか、足りないルールがあったら言ってください。

みなさんはどんなプログラムを考えるのか知りたいという事もあります。ではよろしくお願いします。

　整数列を昇順に並べ直す処理の方が面倒な気もしますけど、とりあえずスクリプトを投下します。以下は一例

	#const N 256
	
	//Step0:乱数初期化
	randomize
	
	//Step1:昇順の集合Ａを作成
	screen 1, 480, 320
	dim a, N
	repeat N-1, 1
		a(cnt) = a(cnt-1)+rnd(3)
		color cnt\16*16+15, 128, cnt/16*16+15
		boxf cnt\16*30, cnt/16*20, cnt\16*30+29, cnt/16*20+19
		color
		pos cnt\16*30, cnt/16*20
		mes a(cnt)
	loop
	
	//Step2:調べる値Ｘを作り、search命令で検索
	x = rnd(N)
	search y, a, x
	
	//Step3:search命令の結果Ｙを出力
	gsel 0
	mes "X="+x
	if y ! -1 {
		repeat length(y)
			mes "A("+y(cnt)+")="+a(y(cnt))
		loop
	} else {
		mes "集合Aの内にXと同値な物は存在せず、ひゃっはー"
	}
	stop
	
	//search命令を突っ込んだモジュール、もうチョイ短くできたかな
#module
	#deffunc search array answer, array group, int target, int offset \
	, local center, local block, local start, local size
	dim answer, 1
	center = length(group)/2
	logmes "center="+center+" : group="+group(center)+" : offset="+offset
	if group(center) ! target {
		if group(center) > target {
			start = 0
			size = center
			logmes "AA"
		} else {
			start = center+1
			size = length(group)-start
			logmes "BB"
		}
		logmes "start="+start+" : size="+size
		if size ! 0 {
			dim block, size
			memcpy block, group, size*4, 0, start*4
			search answer, block, target, offset+start
		} else {
			answer = -1
		}
		return
	}
	answer(0) = center+offset
	repeat -1, 1
		if center-cnt < 0 : break
		if group(center-cnt) ! target : break
		logmes "L="+length(answer)
		answer(length(answer)) = center+offset-cnt
	loop
	repeat -1, 1
		if center+cnt >= length(group) : break
		if group(center+cnt) ! target : break
		logmes "L="+length(answer)
		answer(length(answer)) = center+offset+cnt
	loop
	return
#global

　総当たり処理なら文章量をもっと削る事ができそうです。その分、処理がかさみますけど。以下は一例

#module
	#deffunc search2 array answer, array group, int target \
	, local count
	dim answer, 1
	foreach group
		if group(cnt) = target {
			answer(count) = cnt
			count+
		}
	loop
	return
#global

ソート済み(昇順)なら二分探索安定
個数を調べるところは効率が悪そうですが

	randomize
	it = rnd(100)		// 求める値
	mes "find: " + it
	
	// 昇順の配列を自動生成 (適当)
	repeat 100
		x = cnt
		repeat rnd(3)
			set(i) = x : i ++
		loop
	loop
	
	// 検索 (set(idx) == it となる idx を求める)
	range = 0, length(set) - 1	// 対象区間
	repeat
		mes strf("[%d, %d]", range(0), range(1))
		
		if ( abs(range(0) - range(1)) <= 1 ) {
			idx = range( set(range(1)) == it )
			break
		}
		
		idx = (range(0) + range(1)) / 2	// 区間の中心
		cmp = set(idx) - it
		if ( cmp == 0 ) { break }	// 発見
		range( cmp > 0 ) = idx
	loop
	
	if ( set(idx) != it ) {
		mes "無かった"
		
	} else {
		// 最初のインデックスを求める
		repeat
			if ( idx == 0 ) { break }
			if ( it == set(idx - 1) ) { idx -- } else { break }
		loop
		
		// 値の連続する個数を求める
		repeat length(set) - idx - 1, idx
			len ++
			if ( it != set(cnt + 1) ) { break }
		loop
		
		mes "[" + idx + "] から " + len + " 個"
		
	}
	
	mes "\n参考に [idx] の周囲を表示"
	repeat len + 4, limit(idx - 2, 0, 0xFFFF)
		if ( cnt == length(set) ) { break }
		mes "set(" + cnt + ") = " + set(cnt)
	loop

配列の作成はレノスさんものを参考にさせてもらいました。

;===================配列作成=========================

	v_N = 1000;配列の長さ

	randomize
	v_check = rnd(v_N)		;求める値
	mes "探す数: " + v_check
	

	repeat v_N
		v_x = cnt
		repeat rnd(3)
			a_set(v_i) = v_x
			v_i++
		loop
	loop

	mes "対象配列"
	v_str1 = ""
	foreach a_set
		v_str1 += "a_set(" + cnt + ")=" + a_set(cnt)+"\n"
	loop

	mesbox v_str1,200,200


	wait 200

;===================検索=========================
	mes "検索開始"

	v_MIN = 0
	v_MAX = length(a_set)
	v_i=0

	v_str2 = ""
	repeat
		v_A = (v_MIN + v_MAX) / 2
		if v_MAX - v_MIN <= 1 : break

		v_str2 += "a_set(" + v_A + ")=" + a_set(v_A)+"\n"
		if(a_set(v_A) = v_check){
			a_list(v_i) = v_A
			v_i++

			repeat -1,1
				if a_set(v_A-cnt) = v_check {
					a_list(v_i) = v_A-cnt : v_i++
				} else {
					if a_set(v_A+cnt) = v_check {
						a_list(v_i) = v_A+cnt : v_i++
					} else : break
				}
			loop

			break
		} else {
			if(a_set(v_A) < v_check) : v_MIN = v_A : else : v_MAX = v_A
		}
		wait 1
	loop

	mesbox v_str2,200,50

;=================表示========================
	mes "結果"
	mes str(v_i) + "個一致"

	v_str3 = ""
	repeat v_i
		v_str3 += "a_set(" + a_list(cnt) + ")=" + a_set(a_list(cnt)) + "\n"
	loop

	mesbox v_str3,200,100

dim 集合,100
A=任意の数
数=0
repeat 100
  if(集合(cnt)=A) {mes cnt : 数+=1}
loop
if(数=0) : mes "無かった"

無かった場合も表示すると言うことは、総当たりと同じです。
実行していないので間違っているかも。

簡単に書いたけど、配列は昇順でソートされたものが用意されている
と考えてもいいのかな。じゃないと、配列を作る時点で判っちゃうの
ですが。

>KAさん
結果だけ見ると同じですけど、速度面での効率を考えると同じではないですよ〜
10億個のデータがあった場合、2分探索なら最長でも30回くらいのループで有無がわかりますが
総当りだと平均5億回もループを回さないといけないことに…^^;

ただ、コード行数と開発工数を考えると、総当りもある意味では「効率的」ですよね（^▽^*