در قسمت سوم از مجموعه مقالات چگونه با پایتون برنامه بنویسیم(کدماشین حساب با پایتون)، شما را با اعداد فیثاغورسی آشنا کردیم و در ادامه با نوشتن چند الگوریتم، روش پیدا کردن سه‌تایی‌های فیثاغورسی را آموختیم. در این قسمت تصمیم داریم شما را با نحوه‌ی نوشتن یک برنامه‌ی دیگر درباره‌ی اعداد فیثاغورسی آشنا کنیم. به طور قطع افراد بسیاری به دنبال، راه‌حلی برای حل این سوال بوده و خواهند بود. اگر به برنامه‌نویسی و چالش حل مسئله، علاقه دارید، تا پایان مقاله‌ی بازی با اعداد فیثاغورسی در پایتون را مطالعه کنید.
برنامه‌ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون
در این قسمت، برنامه‌ای می‌نویسیم که عدد n را گرفته و یک سه‌تایی فیثاغورسی از اعداد صحیح که جمع آن برابر با n باشد، را در خروجی نمایش دهد. در صورتی که هیچ سه‌تایی پیدا نکند، گزینه‌ی "No Triplet" را چاپ کند.
برای مثال:
Input : n = 12
Output : 3, 4, 5
اعداد 3، 4 و 5 یک سه تایی فیثاغورسی است، که جمع آنها برابر با 12 است.
Input : n = 4
Output : No Triplet
هیچ سه‌تایی فیثاغورسی وجود ندارد، که جمع آنها برابر با 4 باشد.قبل از اینکه ما برنامه را برای شما بنویسیم، سعی کنید خود راه‌حلی برای آن پیدا کنید و سپس آن را با روش حل ما، مقایسه کنید و سطح دانش برنامه‌نویسی خود را بسنجید.
حل مسئله:
به طور کلی، جواب ما وقتی صحیح است که دو فرمول زیر برقرار باشد:
- n=a+b+c
- a^2+b^2=c^2
ما برای حل این سوال، از دو الگوریتم مختلف استفاده می‌کنیم که در آن الگوریتم دوم از سرعت بالاتری برخوردار خواهد بود. در ادامه با ما همراه باشید.
روش اول برنامه‌ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون:
یک راه‌حل ساده، استفاده از سه حلقه تو در تو، برای پیدا کردن هر کدام از سه‌تایی‌های فیثاغورثی است که در آن بررسی می‌کند که جمع اعداد برابر با n باشد. ولی پیچیدگی زمانی این الگوریتم O(n^2) است، که سرعت بسیار پایینی خواهد داشت.
یک راه‌حل کارآمدتر، استفاده از دو حلقه تو در تو است که حلقهی اول از i=1 تا n/3 اجرا می‌شود و حلقهی دوم از j=i+1 تا n/2 اجرا می‌شود. در حلقهی دوم بررسی می‌شود (n - i - j)^2 برابر با (i*i+ j*j) باشد.
ابتدا برنامه را به صورت کامل قرار می‌دهیم، سپس هر قسمت را توضیح خواهیم داد.
def pythagoreanTriplet(n):
for i in range(1, n//3+1):
for j in range(i+1, n//2+1):
k = n - i - j
if (i*i + j*j == k*k):
print(i, j, k)
return
print ('No Triplet')
number = int(input('Enter input Number: '))
pythagoreanTriplet(number)همان‌طور که ملاحظه می‌کنید، ما کدهای خود را در یک تابع نوشتیم، به این طریق کدی منظم‌تر و زیباتری داریم و برای بهبود بخشیدن به آن در آینده، کار آسان‌تری پیش رو خواهیم داشت..
در تابع، ابتدا یک حلقهی تکرار for از یک تا n/3 را پیمایش می‌کند. در اینجا چون خود عدد n/3 را نیز نیاز داریم، آن را با یک جمع کرده‌ایم. به این صورت:
. . .
for i in range(1, n//3 + 1):
. . .نکته: از آنجایی که برنامه‌ی ما با اعداد صحیح کار می‌کند، n//3 را به کار می‌بریم، تا قسمت صحیح تقسیم محاسبه شود.
سپس در حلقه، یک حلقهی for دیگر قرار می‌دهیم که از i+1 تا n//2 را پیمایش می‌کند. در اینجا نیز یک واحد به حاصل تقسیم n//2 اضافه می‌کنیم. به این صورت:
. . .
for i in range(1, n//3+1):
for j in range(i+1, n//2+1):
. . .تا اینجای کار دو عدد سه‌تایی فیثاغورسی، شامل i و j می‌شود، پس با توجه به فرمول شماره‌ی یک بالا عدد سوم از این رابطه به دست می‌آید.
k = n - i - j
در نتیجه در داخل حلقهی دوم ابتدا این رابطه را قرار می‌دهیم و سپس با یک if بررسی می‌کنیم که فرمول شماره‌ی 2 بالا برقرار باشد. به این صورت:
. . .
for i in range(1, n//3+1):
for j in range(i+1, n//2+1):
k = n - i - j
if (i*i + j*j == k*k):
. . .اگر شرط if ما برقرار باشد، مقادیر سه متغیر i و j و k را به عنوان جواب مسئله، چاپ کرده و با دستور return آن را برگشت داده و از برنامه خار ج می‌شویم. به این صورت:
. . .
for j in range(i+1, n//2+1):
k = n - i - j
if (i*i + j*j == k*k):
print(i, j, k)
return
. . .حال اگر در دو حلقهی تو در توی ما، هیچ کدام از شرایط برقرار نباشد، با خروج از حلقه‌ها، عبارت No Triplet را چاپ می‌کنیم و برنامه پایان می‌یابد. به این صورت:
. . .
for i in range(1, n//3+1):
for j in range(i+1, n//2+1):
k = n - i - j
if (i*i + j*j == k*k):
print(i, j, k)
return
print ('No Triplet')
. . .حال که تابع را نوشتیم، وقت آن است با دریافت یک عدد صحیح از کاربر، تابع را فراخوانی کنیم. به این صورت:
. . .
number = int(input('Enter input Number: '))
pythagoreanTriplet(number)به این طریق برنامه‌ی ما به صورت کامل نوشته شد و اکنون آماده‌ی استفاده کردن است.
روش دوم برنامه‌ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون:
در این روش ما از الگوریتمی استفاده می‌کنیم که فقط یک حلقهی تکرار دارد و پیچیدگی زمانی آن O(n) است که از سرعت بالایی برخوردار است.
روال کار به این صورت است که مقدار b و c را از نظر a پیدا می‌کنیم و a را از 1 تا n تکرار کنیم. برای پیدا کردن مقادیر b و c باید مراحل زیر را دنبال کنیم.
- مانند قبل ما دو رابطه‌ی زیر را خواهیم داشت:
- a^2+b^2=c^2
- a+b+c=n
- از رابطه دوم بالا، c را پیدا کرده و جایگزین رابطه اول می‌کنیم. به این صورت:
از رابطه دوم: c=n-a-b
حال، این مقدار در رابطه اول قرار می‌دهیم: a^2+b^2=(n-b-a)^2
- پس از حل روابط بالا خواهیم داشت:
b = (N * N - 2 * N * a) / (2 * N - 2 * a)
c=n-b-a
- اکنون، از 1 تا n را تکرار کرده و مقادیر b و c را پیدا کرده و بررسی می‌کنیم که a^+b^=C^2
نوشتن کد:
اکنون کد کامل برنامه را در زیر قرار می‌دهیم و در ادامه آن را بررسی می‌کنیم.
def pythagoreanTriplet(n):
for a in range(1, n):
b = (n*n - 2*n*a) // (2*n - 2*a)
c = n - a - b
if (a*a + b*b == c*c and b>0 and c>0):
print (a, b, c)
return
print('No Triplet')
number = int(input('Enter input Number: '))
pythagoreanTriplet(number)در این روش نیز، ما کدهای خود را در یک تابع قرار می‌دهیم تا هم منظم‌تر شود و هم در صورتی که قصد بهبود بخشیدن به کد را داشتیم، کارمان ساده‌تر باشد.
در تابع، ما از یک حلقهی تکرار for استفاده می‌کنیم که از 1 تا n را پیمایش می‌کند. به این صورت:
def pythagoreanTriplet(n):
for a in range(1, n):
. . .در داخل حلقه، با توجه به رابطه‌هایی که برای پیدا کردن b و c به دست آوردیم، متغیرهای b و c را به دست می‌آ‌وریم. به این صورت:
. . .
for a in range(1, n):
b = (n*n - 2*n*a) // (2*n - 2*a)
c = n - a – b
. . .با توجه به روش به دست آوردن b و c ، شرط a+b+c=n برقرار است. اما برای بررسی شرط a^2+b^2=c^2 از یک if استفاده می‌کنیم. ضمن آن که اعداد ما باید از نوع صحیح و مثبت باشند، بررسی می‌کنیم c و b بزرگتر از صفر باشند. به این صورت:
. . .
for a in range(1, n):
b = (n*n - 2*n*a) // (2*n - 2*a)
c = n - a - b
if (a*a + b*b == c*c and b>0 and c>0):
. . .در صورتی که شرط برقرار باشد، برنامه به جواب رسیده، لذا مقادیر a و b و c را چاپ کرده و با دستور return به اجرای برنامه، خاتمه می‌دهیم. به این صورت:
. . .
if (a*a + b*b == c*c and b>0 and c>0):
print (a, b, c)
return
. . .اکنون، اگر حلقه به پایان رسید و برنامه هیچ سه‌تایی فیثاغورسی یافت نکرد، عبارت “No Triplet” را چاپ می‌کنیم.
. . .
for a in range(1, n):
b = (n*n - 2*n*a) // (2*n - 2*a)
c = n - a - b
if (a*a + b*b == c*c and b>0 and c>0):
print (a, b, c)
return
print('No Triplet')
. . .ما تابع را نوشتیم، اکنون نوبت آن است که ورودی را از کاربر دریافت کرده و با آن تابع را فراخوانی کنیم. به این صورت:
. . .
number = int(input('Enter input Number: '))
pythagoreanTriplet(number)برنامه‌ی ما به پایان رسید. این بار برنامه‌ای نوشتیم که n را از کاربر گرفته و بررسی می‌کند، آیا هیچ سه‌تایی فیثاغورسی وجود دارد که مجموع رقم‌هایش برابر با n باشد یا خیر.
این الگوریتمی که به کار بردیم، از سرعت قابل قبولی برخوردار است و با سرعت به جواب خواهد رسید.
برنامه دوم: پیدا کردن اعداد فیثاغورسی در پایتون از یک لیست
در ادامه برنامه‌ای دیگر با موضوع اعداد فیثاغورسی خواهیم نوشت. در این برنامه ما یک لیست شامل اعداد صحیح از کاربر دریافت کرده و سپس بررسی می‌کنیم هیچ سه‌تایی فیثاغورسی در آن هست یا خیر. در صورت وجود سه‌تایی فیثاغورسی عبارت yes در غیر این صورت no را چاپ می‌کنیم.
برای مثال:
input: arr_list = [3, 1, 4, 6, 5]
Output: Yes
سه‌تایی فیثاغورسی (5 ،4 ،3) در این لیست وجود دارند.
Input: arr_list = [10, 4, 6, 12, 5]
Output: No
هیچ سه‌تایی فیثاغورسی در این لیست وجود ندارد.قبل از اینکه ما برنامه را برای شما بنویسیم، سعی کنید خود راه‌حلی برای آن پیدا کنید و سپس آن را با روش حل ما، مقایسه کنید و سطح دانش برنامه‌نویسی خود را بسنجید.
این برنامه نیز مانند برنامه قبلی، با چند روش و الگوریتم متفاوت حل می‌شود، که ما یک روش را برای شما توضیح می‌دهیم.
نوشتن برنامه:
ساده‌ترین روش، برای نوشتن برنامه‌ای برای حل این سوال، استفاده از سه حلقهی تو در تو است. سه حلقه، تمامی عناصر لیست را بررسی می‌کنند تا سه‌تایی فیثاغورسی در آن وجود دارد یا خیر.
ابتدا برنامه‌ی کامل را در زیر ببینید، سپس آن را به صورت مختصر توضیح می‌دهیم.
def isTriplet(ar, n):
j = 0
for i in range(n - 2):
for k in range(j + 1, n):
for j in range(i + 1, n - 1):
# Calculate square of array elements
x = ar[i]*ar[i]
y = ar[j]*ar[j]
z = ar[k]*ar[k]
if (x == y + z or y == x + z or z == x + y):
return 1
# If we reach here, no triplet found
return 0
# Driver program to test above function
ar_list = list(map(int, input('Enter Numbers list: ').split(' ')))
if isTriplet(ar_list, len(ar_list)):
print("Yes")
else:
print("No")ابتدا ما یک تابع می‌نویسیم که دو ورودی دریافت می‌کند، اولین آیتم لیست اعداد صحیح و آیتم دوم طول لیست است.
def isTriplet(ar, n):
. . .قبل از هر چیز، متغیر j را با صفر مقداردهی می‌کنیم، سپس سه حلقهی تو در تو for می‌نویسیم که هر کدام به ترتیب این‌گونه تکرار می‌شوند:
حلقهی اول از صفر تا n-2
حلقهی دوم از j+1 تا n
حلقهی سوم از i+1 تا n-1
. . .
j = 0
for i in range(n - 2):
for k in range(j + 1, n):
for j in range(i + 1, n - 1):
. . . در حلقهی سوم، برای منظم‌تر شدن کد، مربع اعداد را در متغیرهای x، y و z قرار می‌دهیم و سپس با یک شرط بررسی می‌کنیم که رابطه‌ی a^2+b^2=c^2 برای این متغیرها برقرار است یا خیر. به این صورت:
. . .
x = ar[i]*ar[i]
y = ar[j]*ar[j]
z = ar[k]*ar[k]
if (x == y + z or y == x + z or z == x + y):
. . .اگر شرط برقرار باشد، True را با دستور return باز می‌گردانیم و برنامه از تابع خارج می‌شود. در غیر این صورت در پایان، تابع False را return می‌کنیم. به این صورت:
def isTriplet(ar, n):
j = 0
for i in range(n - 2):
for k in range(j + 1, n):
for j in range(i + 1, n - 1):
x = ar[i]*ar[i]
y = ar[j]*ar[j]
z = ar[k]*ar[k]
if (x == y + z or y == x + z or z == x + y):
return 1
return 0
. . .بعد از نوشتن تابع، ما نیاز داریم لیست خود را از کاربر دریافت کنیم. برای این کار ما می‌توانیم از یک حلقهی تکرار استفاده کنیم یا خیلی ساده از قدرت پایتون استفاده کرده و با یک خط کد، کل لیست را دریافت کنیم. به این صورت:
ar_list = list(map(int, input('Enter Numbers list: ').split(' ')))در پایان، خروجی تابع نوشته شده را با یک if بررسی کرده و در صورت درستی، Yes را و در غیر این صورت No را چاپ می‌کنیم. به این صورت:
. . .
if isTriplet(ar_list, len(ar_list)):
print("Yes")
else:
print("No")
. . .برنامه‌ی نوشته شده‌ی ما در این روش، دارای پیچیدگی زمانی O(n^3) است. برای نوشتن این برنامه از الگوریتم‌ها و روش‌های دیگری نیز می‌توان استفاده کرد که اگر علاقه‌مند هستید مقاله‌ی Pythagorean Triplet in an array را مطالعه کنید.
جمع بندی
پایتون، زبان برنامه‌نویسی بسیار ساده و در عین حال قدرتمندی است که قادر به نوشتن برنامه‌های متنوعی بوده و خواهد بود. ما سعی داریم با نوشتن برنامه‌های کوچک و کاربردی قدرت این زبان برنامه‌نویسی را برای شما ثابت کنیم.در مقاله‌ی بازی با اعداد فیثاغورسی در پایتون، ملاحظه کردید سوالاتی که در ابتدا بسیار مشکل می‌نمود با کمی تفکر و خلاقیت، با اندکی کدنویسی و بسیار ساده حل شد. یک برنامه‌نویس نباید توانایی‌های خود را دست کم بگیرد، بلکه باید با صبر و حوصله و کمی تحقیق به جواب سوالات خود برسد.
اگر به یادگیری بیشتر در زمینه‌ی برنامه نویسی پایتون علاقه داری، یادگیری زبان پایتون بسیار ساده است. و با شرکت در دوره‌ی آموزش پایتون توسعه وب در آینده می‌تونی اپلیکیشن موبایل و دسکتاپ بسازی و وارد حوزه‌ی هوش مصنوعی هم شوی.