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

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

新規登録して質問してみよう
ただいま回答率
86.02%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

整数 Nが与えられたときの2^Nを10で割った余りを計算しなさい

bamboooo
bamboooo

総合スコア5

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

3回答

0グッド

0クリップ

379閲覧

投稿2023/01/18 13:18

前提

アルゴ式で競プロの勉強した際に出てきたプログラムが理解できない

理解できない点

・4行目のreturn 1がどのような処理を行っているのか
・7~11行目がどのような処理を行っているのか

発生している問題

「整数 Nが与えられたときの2^Nを10で割った余りを計算しなさい」という問題のサンプルプログラムが理解できない

該当のソースコード

python3

1def calc(N): 2 # 終端条件 3 if N == 0: 4 return 1 5 6 # たとえば 2^10 = 2^5 * 2^5、2^11 = (2^5 * 2^5) * 2 7 half = calc(N // 2) 8 res = half * half 9 if N % 2 == 1: 10 res *= 2 11 return res % 10 12 13N = int(input()) 14print(calc(N))

試したこと

・「return1 意味」、「python 戻り値」などと検索する
・再帰関数について調べる

以下のような質問にはグッドを送りましょう

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

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

気になる質問をクリップする

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

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

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

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

適切な質問に修正を依頼しましょう。

回答3

2

前半部分は累乗計算を再帰で記述していますね。
2 ^ ( N / 2)を計算し、これを自乗しています。なお、Nが奇数の場合はさらに2をかけます。
終了条件として、Nがゼロならば1を返すことと定義しています。

この方法であれば、Nの値に対する時間計算量がO(logN)となります。N回乗算する場合はO(N)なので、より小さいオーダになります。

投稿2023/01/18 13:43

編集2023/01/18 13:46
HogeAnimalLover

総合スコア4823

bamboooo, yukkuri_55👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

2023/01/18 14:07

こちらの回答が他のユーザーから「質問に対する回答となっていない投稿」という指摘を受けました。

0

ベストアンサー

簡単に、Nが2の整数乗(2,4,8,16,32,64,...)の場合を考えてみましょう。

たとえばN=8つまり「2^8乗を10で割った余り」を求めるとします。
8= 4 + 4 なので
「2^8乗を10で割った余り」は

  • (2^4乗を10で割った余り × 2^4乗を10で割った余り)を10で割った余り

と分解できます。

同様に、「2^4乗を10で割った余り」は 4=2+2 なので

  • (2^2乗を10で割った余り × 2^2乗を10で割った余り)を10で割った余り

で計算できます。
このように分解していくと最後に

  • (2^0乗を10で割った余り × 2^0乗を10で割った余り)を10で割った余り
  • =(1 × 1)を10で割った余り
  • = 1

となります。
これが

py

1 # 終端条件 2 if N == 0: 3 return 1

の部分です。

上の例を一般化して、プログラムでは
与えられた数をどんどん 2 で割っていく ( half = calc(N // 2) )
→ その数を10で割った余り [ calc(N // 2)] を求めて、2乗する。(res=half*half)
→ res を10で割った余りを求めて返す( return res % 10)

という手順を踏んでいます。


ではNが奇数(奇数乗)の場合はどう計算すればよいのでしょうか。

たとえば N=7のとき(2^7乗を10で割った余り)の計算を考えてみましょう

このときは
7=3+3+1なので

  • (2^3乗を10で割った余り × 2^3乗を10で割った余り × 2^1乗 を10で割った余り)を10で割った余り

を求めればいいわけですね。

3つ目の「2^1乗 を10で割った余り」はすなわち 2 なので

  • (2^3乗を10で割った余り × 2^3乗を10で割った余り × )を10で割った余り

を求めることになります。

この後半の「× 2」が

py

1 if N % 2 == 1: res *= 2

の部分の意味です。

投稿2023/01/18 16:59

編集2023/01/18 17:12
qnoir

総合スコア7834

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

0

calc(N) = mod10(2^N)なので
Nが奇数のとき、N=2k+1とおくと calc(N) = mod10(2✖️(2^2k)) = mod10(2✖️mod10(2^k)^2) = mod10(2✖️calc(k)^2)
Nが偶数のとき、N=2kとおくとcalc(N) = mod10(2^2k) = mod10(mod10(2^k)^2) = mod10(calc(k)^2)
それぞれ分解できる。つまり、calc(k)が解っていれば、calc(2k)かcalc(2k+1)の計算を返せる。 これが7-11行目の処理。おなじくcalc(k)はcalc(2j)かcalc(2j+1)をつかって計算できるので、どんどんNを小さくしてcalcを呼び出していき、最後はcalc(0)にたどり着く。この値はmod10(2^0)=1。

たとえばcalc(5)なら、mod10(2✖️calc(2)^2)なので、calc(2)を呼んで、calc(2)=mod10(calc(1)^2)なので、calc(1)を呼んで、calc(1)=mod10(2✖️calc(0)^2)なので、calc(0)を呼ぶ。
calc(0)で4行目のreturnにたどり着くと、そこから呼び出し(途中の計算)が戻っていく。
calc(0)=1, calc(1)=mod10(2✖️1^2)=2, calc(2) = mod10(2^2)=4, calc(5)=mod10(2✖️4^2)=2

投稿2023/01/18 13:50

編集2023/01/18 15:39
matukeso

総合スコア1427

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

回答へのコメント

bamboooo

2023/01/18 15:10

とてもわかりやすい解説で納得できました。ありがとうございます。 解説を読んで湧いてきた質問なのですが、9,10行目のNが奇数の際にresを2倍するという処理はなぜ行うのでしょうか。
matukeso

2023/01/18 15:35 編集

Nが奇数のとき、N=2k+1とおくと、の文が理解できないということですか? 2^(2k+1)=2✖️((2^k)^2)で、resは(2^k)^2を意味しているからですが。
bamboooo

2023/01/18 15:51

ソースコードの9,10行目のif N % 2 == 1: res *= 2の部分が理解できないという意味です。 質問の仕方がわかりにくくてすみません。

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

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。