برنامه ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون
روش اول برنامه ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون:
روش دوم برنامه ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون:
برنامه دوم: پیدا کردن اعداد فیثاغورسی در پایتون از یک لیست
در قسمت سوم از مجموعه مقالات چگونه با پایتون برنامه بنویسیم(کدماشین حساب با پایتون)، شما را با اعداد فیثاغورسی آشنا کردیم و در ادامه با نوشتن چند الگوریتم، روش پیدا کردن سه تاییهای فیثاغورسی را آموختیم. در این قسمت تصمیم داریم شما را با نحوه ی نوشتن یک برنامه ی دیگر درباره ی اعداد فیثاغورسی آشنا کنیم. به طور قطع افراد بسیاری به دنبال، راه حلی برای حل این سوال بوده و خواهند بود. اگر به برنامه نویسی و چالش حل مسئله، علاقه دارید، تا پایان مقاله ی بازی با اعداد فیثاغورسی در پایتون را مطالعه کنید.
برنامه ی پیدا کردن اعداد فیثاغورسی یک عدد در پایتون
در این قسمت، برنامه ای مینویسیم که عدد 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
. . .
بعد از نوشتن تابع ، ما نیاز داریم لیست خود را از کاربر دریافت کنیم. برای این کار ما میتوانیم از یک حلقه ی تکرار استفاده کنیم یا خیلی ساده از قدرت پایتون استفاده کرده و با یک خط کد، کل لیست را دریافت کنیم. به این صورت:
برنامه ی نوشته شده ی ما در این روش، دارای پیچیدگی زمانی O(n^3) است. برای نوشتن این برنامه از الگوریتمها و روشهای دیگری نیز میتوان استفاده کرد که اگر علاقه مند هستید مقاله ی Pythagorean Triplet in an array را مطالعه کنید.
جمع بندی
پایتون، زبان برنامه نویسی بسیار ساده و در عین حال قدرتمندی است که قادر به نوشتن برنامه های متنوعی بوده و خواهد بود. ما سعی داریم با نوشتن برنامههای کوچک و کاربردی قدرت این زبان برنامه نویسی را برای شما ثابت کنیم.
در مقاله ی بازی با اعداد فیثاغورسی در پایتون، ملاحظه کردید سوالاتی که در ابتدا بسیار مشکل مینمود با کمی تفکر و خلاقیت، با اندکی کدنویسی و بسیار ساده حل شد. یک برنامه نویس نباید تواناییهای خود را دست کم بگیرد، بلکه باید با صبر و حوصله و کمی تحقیق به جواب سوالات خود برسد.
اگر به یادگیری بیشتر در زمینه ی برنامه نویسی پایتون علاقه داری، یادگیری زبان پایتون بسیار ساده است. و با شرکت در دوره ی آموزش پایتون توسعه وب در آینده میتونی اپلیکیشن موبایل و دسکتاپ بسازی و وارد حوزه ی هوش مصنوعی هم شوی.