この記事では、再帰を使って、配列内の要素の最初、最後、およびすべての出現回数を求めます。
問題文に入る前に、まずRecursionとは何かを理解しましょう。
Recursionについて学びたい方は、Recursionについて知るためのリンクが用意されています。
Recursionについて学ぶには、こちらをご覧ください。
要素の最初の出現箇所を探す
まず、Pythonの配列の中で要素が最初に出現する場所を探してみましょう。
要素のリスト（配列）の中で、その要素が出現する最初の位置を見つけることが目的です。
例として
与えられた配列==> [1,2,3,4,2] です。
この問題の解を求めるには、次のような手順で行います。
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the first element is equal to X if found then return
Step 4 : Otherwise recursively go by slicing the array and incrementing and decremementing the itrerator and n value (size of array ) respectively
Step 5 : Repeat until the element is found or not
|
上記のステップのコード実装は以下の通りです。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print("Element present at position 1")
else:
print("Element not found")
return
# More than one element
else:
if(arr[0] == x):
print("Found at position: ", itr+1)
else:
find_first(arr[1:],n-1,x,itr+1)
return
arr = [1,2,3,4,5,2,10,10]
n = len(arr)
x = 10
itr = 0
find_first(arr,n,x,itr) |
結果は以下の通りです。
Found at position: 7
|
この記事もチェック：pythonの配列(リスト)の中で最も多い数を見つける方法を解説(コード付き)
あるオブジェクトの最後の出現箇所を探す
次に、Pythonを使って要素の最後の出現位置を探してみます。
要素のリスト(配列)の中で、その要素が最後に出現する位置を見つけることが目的です。
例として
与えられた配列==> [1,2,3,4,2] です。
この問題の解を求めるには、次のような手順で行います。
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then check the first element with X and return the answer if found
Step 3 : For more than one element, we will check if the last element is equal to X if found then return
Step 4 : Otherwise recursively go by slicing the array and decremementing both the iterator and n value (size of array )
Step 5 : Repeat until the element is found or not
|
上記のステップをPythonで実装する
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print("Element present at position 1")
else:
print("Element not found")
return
# More than one element
else:
if(arr[n-1] == x):
print("Found at position: ", itr+1)
else:
find_first(arr[:-1],n-1,x,itr-1)
return
arr = [1,2,3,4,5,2,3,2,3,2,10,10]
n = len(arr)
x = 2
itr = n - 1
find_first(arr,n,x,itr) |
結果を出力すると、以下の様になります。
Found at position: 10
|
オブジェクトの全出現箇所を検索する
ここでは、要素のリスト（配列）において、その要素が出現するすべての位置を見つけることを目的としています。
出現位置には、配列内の要素の最初の位置、最後の位置、および任意の中間位置が含まれます。
例として
与えられた配列==> [1,2,3,4,2] です。
この問題の解を求めるには、次のような手順で行います。
Step 1 : Check if list is empty then return that list is empty
Step 2 : Check if there is only one element then print the position of the element and return
Step 3 : For more than one element, we will check if the first element is equal to X if found then print and keep on recursively calling the function again by slicing the array and decremementing n value (size of array ) and incrementing the value of iterator
Step 5 : Repeat until all the elements are encountered.
|
上記のステップをPythonで実装する
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
def find_first(arr,n,x,itr):
# check if list is empty
if(n==0):
print("List empty!")
return
# Only one element
elif(n==1):
if(arr[0]==x):
print(itr+1,end=" ")
else:
print("Element not found")
# More than one element
else:
if(arr[0] == x):
print(itr+1,end=" ")
find_first(arr[1:],n-1,x,itr+1)
arr = [1,2,10,3,4,10,5,2,10,2,3,10]
n = len(arr)
x = 10
itr = 0
print("Found at position: ",end="")
find_first(arr,n,x,itr) |
結果を出力すると、以下の様になります。
Found at position: 3 6 9 12
|
まとめ
このチュートリアルが終わるころには、与えられた配列の中で要素の最初、最後、そしてすべての出現回数を見つけることに精通していることでしょう。
読んでくれてありがとうございました。