| כותב |
|
אורי גורן
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 23 October 2005 בשעה 23:06 | | IP רשוּם
|
|
|
|
כתוב פונקציה IsSqr שמקבלת מספר שלם n
מחזירה אמת רק אם n הוא ריבוע של מספר שלם אחר
אסור להעזר בכפל,חילוק,העלאה בחזקה והוצאת שורש.
יש לכתוב את הפונקציה בסיבוכיות מינימלית (יעיל ככל האפשר)
|
| חזרה לתחילת העמוד |
|
| |
ברנש מוזר
משתמש מתחיל
הצטרף / הצטרפה: 17 October 2005
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 24 October 2005 בשעה 00:41 | | IP רשוּם
|
|
|
|
הדבר הראשון שעלה לי לראש, לא בטוח שזאת הדרך היעילה ביותר (בטח יש שיטה יותר פשוטה מזאת).
קוד:
#include <stdio.h>
int sqrUp(int n)
{
int i=0,sum=0;
for(i=0;i<n;i++)
sum+=n;
return sum;
}
int isSqr(int n)
{
int i=0;
for(i=0;i<10000;i++)
if(n==sqrUp(i))
return 1;
return 0;
}
int main()
{
int k=0;
scanf("%d",&k);
printf("%d\n",isSqr(k));
return 0;
}
|
|
|
__________________
root@polygonix:~# apt-get moo
moooooooo...wazup
|
| חזרה לתחילת העמוד |
|
| |
SBD
פורומיסט על
הצטרף / הצטרפה: 13 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 1194
|
| נשלח בתאריך: 24 October 2005 בשעה 00:48 | | IP רשוּם
|
|
|
|
אני חושב שהדך הכי פשוטה ויעילה, חוץ מהפאשרות של לכתוב פונקציה שמחשבת שורש בלי הפעועלות הנ"ל....יהיה לעבור על המספרים בטטוח של X/2 כאשר X מציין את המספר...ולבדוק האם I*I == X....זה מה שעולה לי לראש לפחות....
__________________
~ Nobody Is Perfect, I'm Nobody ~
פורומים
|
| חזרה לתחילת העמוד |
|
| |
ברנש מוזר
משתמש מתחיל
הצטרף / הצטרפה: 17 October 2005
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 24 October 2005 בשעה 00:51 | | IP רשוּם
|
|
|
|
השאלה אם אתה יכול לעשות את זה בלי חילוק וכפל. יש גם את שיטת ניוטון אבל
גם היא דורשת חילוק וכפל. הקיצר אם תוכל לכתוב את השיטה שלך בשפת סי זה
יהיה גם נהדר.
__________________
root@polygonix:~# apt-get moo
moooooooo...wazup
|
| חזרה לתחילת העמוד |
|
| |
אורי גורן
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 24 October 2005 בשעה 02:47 | | IP רשוּם
|
|
|
|
אין צורך ממש להעלות בריבוע, להכפיל או לחלק
משום שמימוש הפעולות האלו גוזל זמן ומעלה את הסיבוכיות.
תנסה לחשוב על תכונות של מספרים ריבועיים שמייחדות
אותם מכלל המספרים הטבעיים.
אני לא יכול להרחיב יותר - משום שזה כבר רמז די גדול...
|
| חזרה לתחילת העמוד |
|
| |
ברנש מוזר
משתמש מתחיל
הצטרף / הצטרפה: 17 October 2005
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 24 October 2005 בשעה 03:26 | | IP רשוּם
|
|
|
|
קשה לי לחשוב לעומק, אבל הדבר היחיד שמצאתי לגביהם הוא ש:
קוד:
| Sum=0+1+3+5+7+9....+(n/2)*(2+2(n-1)) |
|
|
עבור n=0,1,2,3...,N
והקוד (בתקווה שהייתי קרוב יותר) :
קוד:
#include <stdio.h>
#define L 100
int isSqr(int n)
{
int i=0,sum=0;
for(i=1;i<L;i++)
{
sum+=i+i-1;
if(n==sum)
return i;
}
return 0;
}
int main()
{
int k=0;
scanf("%d",&k);
printf("%d\n",isSqr(k));
return 0;
}
|
|
|
__________________
root@polygonix:~# apt-get moo
moooooooo...wazup
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 24 October 2005 בשעה 11:26 | | IP רשוּם
|
|
|
|
קודם כל העברתי למדע המחשב...לא יודע למה בהודעה הראשונה שם אף אחד לא ענה...
הממ...סלחו לי על הנטייה שלי לפסקל :)
מה מיוחד ב-0,1,4,9,16,25,36,49,56,64,81,100,...
לא צריך לדעת יותר מדי פסקל כדי להבין את הפונקציה...
קוד:
function isSqr(num:integer):boolean;
var
step,n:integer;
found:boolean;
begin
step:=1;
n:=0;
while n<num do
begin
n:=n+step;
step:=step+2;
end;
isSqr:=(n=num);
end; |
|
|
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
SBD
פורומיסט על
הצטרף / הצטרפה: 13 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 1194
|
| נשלח בתאריך: 24 October 2005 בשעה 13:46 | | IP רשוּם
|
|
|
|
צודק SHOSHAN אחי, איך לא חשבתי על זה =\
__________________
~ Nobody Is Perfect, I'm Nobody ~
פורומים
|
| חזרה לתחילת העמוד |
|
| |
אורי גורן
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 24 October 2005 בשעה 15:31 | | IP רשוּם
|
|
|
|
מכיוון ששלחתי את החידה הזו לפורום נוסף,
אנא עיינו בתגובה הבאה:
http://www.tapuz.co.il/tapuzforum/main/Viewmsg.asp?forum=631 &msgid=64255077
|
| חזרה לתחילת העמוד |
|
| |
ברנש מוזר
משתמש מתחיל
הצטרף / הצטרפה: 17 October 2005
משתמש: מנותק/ת
הודעות: 26
|
| נשלח בתאריך: 24 October 2005 בשעה 15:45 | | IP רשוּם
|
|
|
|
וואלה קצת ארתימטיקה לא הרגה אף אחד. טוב לדעת את הדברים האלה, יאללה עוד חידה.
__________________
root@polygonix:~# apt-get moo
moooooooo...wazup
|
| חזרה לתחילת העמוד |
|
| |
SBD
פורומיסט על
הצטרף / הצטרפה: 13 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 1194
|
| נשלח בתאריך: 24 October 2005 בשעה 16:29 | | IP רשוּם
|
|
|
|
אבל אמרת בלי חילוק לא?
__________________
~ Nobody Is Perfect, I'm Nobody ~
פורומים
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 24 October 2005 בשעה 17:05 | | IP רשוּם
|
|
|
|
הפתרונות:
פתרון החידה
האלגוריתם מבוסס על העובדה שמספר הוא ריבועי
רק אם יש לו מספר אי זוגי של מחלקים |
int IsSqr(int n)
{
int i,j,d=0;
for (i=2,j=n-1;i<=j;i++,j--)
if (n%i==0) d++;
return ((d%2) || (n==1));
} |
האלגוריתם מבוסס על זה שכל מספר ריבועי הוא סכום מהצורה
S=1+3+5+7+...+2k+1 |
|
int IsSqr(int n)
{
int i,s=0;
for(i=1 ; s < n ;i+=2)
s+=i;
return (s==n);
} |
בעקרון הסיבוכיות של הפתרון השני שם (שזה מה שאני הבאתי ולא בגלל שראיתי את זה אי פעם לפני) יותר נמוכה בגלל ש[בכל מקרה לפי דעתי] הסיבוכיות של שארית היא N ושל חיבור היא 1...
עריכה: אני מצטרף להצעה של ברנש מוזר...
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 24 October 2005 בשעה 17:15 | | IP רשוּם
|
|
|
|
עכשיו, אורי בקשר לאתר שלך...אם יש לך כוח הוא דורש שדרוגי אבטחה דחופים דחופים...
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורי גורן
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 24 October 2005 בשעה 17:25 | | IP רשוּם
|
|
|
|
שלח לי בבקשה לאי מייל, (או דרך האתר)
כמה תיקונים דחופים, ואני אתקן....
אם כי - יש לי מבחן ביום ראשון בטכניון - ואני לא בטוח שאני אוכל לתקן זאת בקרוב
תודה מראש !
|
| חזרה לתחילת העמוד |
|
| |
SBD
פורומיסט על
הצטרף / הצטרפה: 13 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 1194
|
| נשלח בתאריך: 24 October 2005 בשעה 17:50 | | IP רשוּם
|
|
|
|
ליפ דעתי השימוש במודל אסור, זה חילוק לכל דבר...
__________________
~ Nobody Is Perfect, I'm Nobody ~
פורומים
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 24 October 2005 בשעה 20:05 | | IP רשוּם
|
|
|
|
OK שלחתי כמה...
זה לא עד כדי כך דחוף...המסחן יותר חשוב...
עריכה: תירשם אני לא יכול לשלוח לך הודעות אישיות...יש כמה דברים שחשוב שתדע...
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
clocker
משתמש מתחיל
הצטרף / הצטרפה: 24 October 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 10
|
| נשלח בתאריך: 25 October 2005 בשעה 14:53 | | IP רשוּם
|
|
|
|
נרשמתי
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 25 October 2005 בשעה 16:32 | | IP רשוּם
|
|
|
|
ברוכים הבאים... :)
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
