iT邦幫忙

5

[自學Python紀錄] HackerRank 新手30天挑戰-Day09

Hi there! 我是嘟嘟~受到前輩啟發,想說可以紀錄一下自己練習的過程,小女子為程式菜逼八,此系列非教學文,僅為個人解題筆記,可能有錯誤或未補充詳盡之處,歡迎前輩們不吝指教!也歡迎正在自學的夥伴一起討論學習~


Day 9: Recursion 3 (遞迴)

輸入格式

輸入一個整數n,作為函式factorial()的參數
注意:如果您無法使用遞迴或未能將遞迴函數命名為階乘或階乘,則得分為。
If you fail to use recursion or fail to name your recursive function factorial or Factorial, you will get a score of 0 .

輸出格式

建立一個函式factorial(n),並印出n的階乘,代表從 1 開始連乘直到 n 為止,意即 n! = 1 x 2 x ... x n

樣本輸入

3

樣本輸出

6

題目原始格式

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the factorial function below.
def factorial(n):

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    result = factorial(n)

    fptr.write(str(result) + '\n')

    fptr.close()

  

我的解答1

from functools import reduce #導入函數reduce

n = int(input()) 

def factorial(n):
    def prod(x,y): 
        return x*y
    seq = [i for i in range(1,n+1)] #生成一個1~n的列表
    return reduce(prod,seq) #對列表的前兩個元素相乘後,再與後一個元素相乘,直到乘完所有元素
print(factorial(n))

第一個想法是導入reduce()函數,但因為題目要求一個factorial()函式才會判斷通過,就變成要在多包裝一次,後來才發現是自己太菜逼八,還不懂遞迴函數的概念,修改後,看起來更簡潔直觀了:
  

我的解答2

n = int(input())

def factorial(n):
    return 1 if n == 1 else n*factorial(n-1)

print(factorial(n))

輸入 10
結果為 3628800
  

補充:

遞迴基本概念 (Recursion)

將大問題拆分成一個個小問題,再各自將小問題解決以後得到答案,稱為分治法(Divide and Conquer),遞迴這個方法就是依據此概念形成的。

在數學以及電腦科學的領域當中,當一個函式會在執行當中,會不斷地自己呼叫自己時,我們便認為這個函式具有遞迴的性質。同時,為了避免函式永無止盡地自我呼叫 (self-calling),我們也需要設計一個明確的終止條件。因此,我們便得到了設計一個遞迴函式的兩個重點:

  1. 遞迴自我呼叫的方式 以及
  2. 結束呼叫的終止條件

最常用到遞迴的情況是?

  1. 階乘 Factorial
  2. 費氏數列 Fibonacci sequence
  3. 最大公因數 GCD

1 則留言

3
一級屠豬士
iT邦大師 1 級 ‧ 2020-05-05 18:12:52

基本上,大多數能被遞迴解決的問題,都可以找出迴圈解。如果使用遞迴的概念解題,通常可以將艱難的問題用簡單的想法解決;但是使用迴圈來改寫的話,通常可以增進程式運行的效率。
上面這段大錯特錯!!! 要是這樣簡單二分,迴圈勝過遞迴,那真是太簡單的世界了.
可惜不是.

初學者其實不需要到處去找一堆解釋,像心原一馬就很愛寫一些他個人看法,也不只他這樣,
現在有很多人寫blog,或是文章,雖然很好心的解釋.但是初學者最好不要貪圖快速,把這些
好心人的結論快速的烙印進去,而是要逐步的練習領悟.

最好是看書,這類的解題網站,我個人看法是進度太過快了.

看更多先前的回應...收起先前的回應...
Pondudu iT邦新手 5 級 ‧ 2020-05-05 18:26:03 檢舉

瞭解,已修正!小的會再更謹慎一點的!!
/images/emoticon/emoticon70.gif
非常感謝您的閱讀和建議!!
/images/emoticon/emoticon41.gif

心原一馬 iT邦研究生 5 級 ‧ 2020-05-05 21:22:13 檢舉

你好:
針對你提出的觀點進行討論,
我同意自己的文章會加入蠻多個人看法的,
當然很多人也會,
不過這有什麼問題嗎?
我在我自己的部落格寫文章,我不寫我的個人想法,難道我要直接抄教科書的內容嗎?

我也發表一下個人看法,
我覺得解題網站不會進度太快啊,
而且解題網站跟書本相比有其好處- 互動性

解一道題目的時候,透過上傳程式碼,
解題網站告訴你哪些測資會錯,
需要一步步的修正程式碼使得邏輯正確,
即是練習領悟的過程

而且解題網站也有簡單題與難題,
從基礎題程式邏輯簡單的開始練習,
算是可接受的,
並不是說一開始就去挑leetcode的超難題來挑戰

我是誇獎你啊.說你是好人啊,有心分享啊.
我是勸她別光只是找,查看,單純吸收,也要自己多思考.
也鼓勵你可以多回答問題,這也是一種互動.

心原一馬 iT邦研究生 5 級 ‧ 2020-05-05 22:53:53 檢舉

哦哦~ 不好意思小馬會錯意,
以為你在說文章寫個人想法是不好的,
那沒問題了,謝謝指教~

至於回答問題嘛…
我是覺得iT邦的問答區蠻多人都不給最佳解答的,
問完問題就消失也不說聲謝謝的,
現在我在回答問題前都會稍微看一下他的發問記錄,
常常不給最佳解答者就比較沒意願答就是了
(不過到小馬的文章問問題我還是蠻樂意互動回答的)

蠻多人都不給最佳解答 , 這是老問題了.也不只這裡如此.
以前還有刪文,然後整串消失,很可惜的.後來經過許多人反應,
才改的.
回答問題,有些是很精彩的.

我要留言

立即登入留言