当コードは、Codilitiyというコーディングテストのサイトの問題を自分で解いたコードです。

問題内容は、Aにはいるリストの各数値に対して割り切れる数値がリスト内に何個あるかをカウントしたリストを返すという問題です。

問題は解くことができたのですが、二重ループをつかった解法しかかけず、分割統治法でどうにかいけないかと模索しています。

なにか、お気づきの点ありましたらご教示いただけますと助かります。

brute force式の解法

python
1A = [3,1,2,3,6]
2count = []
3for xi in range(len(A)):
4    count.append(0)
5    for yi in range(len(A)):
6        if A[xi]%A[yi] != 0 and A[xi]!= A[yi]:
7            count[xi]+=1

アウトプット

[2, 4, 3, 2, 0]

＊アウトプットの補足
A[0] = 3, the non-divisors are: 2, 6、したがって割り切れない数値は2個
A[1] = 1, the non-divisors are: 3, 2, 3, 6,したがって割り切れない数値は4個
A[2] = 2, the non-divisors are: 3, 3, 6,したがって割り切れない数値は3個
A[3] = 3, the non-divisors are: 2, 6,したがって割り切れない数値は2個
A[4] = 6, there aren't any non-divisors.したがって割り切れない数値は0個

＊参照URL
stackoverflow

行動規範の内容に同意します

回答1件

分割統治法は、扱うデータのサイズを小さくして再帰呼出しを使うやり方です。
1つ小さいサイズのデータで再帰させることによって、ループを無くせます。

Python
1def bf(A):
2	count = []
3
4	def y(i, j):
5		return y(i, j-1) + (A[i-1] % A[j-1] != 0) if j != 0 else 0
6
7	def x(i):
8		if i != 0:
9			x(i-1)
10			count.append(y(i, len(A)))
11
12	x(len(A))
13	return count
14
15A = [3, 1, 2, 3, 6]
16C = bf(A)
17print(C)

追記

問題内容は、Aにはいるリストの各数値に対して割り切れる数値がリスト内に何個あるかをカウントしたリストを返すという問題です。

A[0] = 3, the non-divisors are: 2, 6、したがって割り切れない数値は2個

質問には、「割り切れる数値」と「割り切れない数値」いう矛盾した記述があります。
the non-divisors are とあるので、「約数でないもの」と言い換えたほうが良いのではありませんか？
質問は編集できます。
また、回答にはコメントをお願いします。

追記2
x と y を関数bf の内部関数にしたのは、bf のローカル変数 count にアクセスするためです。
count をグローバル変数にすると、x と y は bf の外に出せます。

Python
1def y(i, j):
2	return y(i, j-1) + (A[i-1] % A[j-1] != 0) if j != 0 else 0
3
4def x(i):
5	if i != 0:
6		x(i-1)
7		count.append(y(i, len(A)))
8
9def bf(A):
10    x(len(A))
11
12count = []
13A = [3, 1, 2, 3, 6]
14bf(A)
15print(count)