ערכתי לאחרונה בתאריך 08.02.09 בשעה 03:46 בברכה, Deuce
אז ככה - הפתרון הראשון והפחות יעיל שלי מבוסס על מה שאמרתי למעלה, רק שאני מוסיף Set שאליו אני מכניס פרמוטציות. זוהי קבוצה ולכן לא נכניס פרמוטציות זהות של מקדמים. זה לא יעיל במיוחד מהבחינה שעבור 1+1+2 למשל אני אבצע 3 איטרציות במקום 1.
הסיבוכיות לא מטורפת אך זה לא מספיק יעיל.
בכל מקרה קוד ב-JAVA:
public static void foo(int[] Numbers , int[] Coefficient , int result
, TreeSet<String> Set) {
int sum = 0;
String Str = ""; for (int i=0 ; i<Numbers.length; i++) {
sum += Coefficient[i]*Numbers[i];
Str = Str + Coefficient[i];
} if (sum > result)
return;
if (sum == result) {
Set.add(Str);
return;
}
for (int i = 0; i < Numbers.length; i++) {
int[] CoefficientNew = Coefficient.clone();
CoefficientNew[i]++;
foo(Numbers , CoefficientNew , result , Set);
}
}
|
תכנית ראשית:
public static void main(String[] args) { int[] Numbers = {1,4,10};
int[] Ar = new int[3];
TreeSet<String> Set = new TreeSet<String>(); foo(Numbers,Ar,10,Set);
System.out.println(Set.size());
|
הפלט הוא 4 כפי שמצופה.
אפשר לייעל את זה לפני כניסה לצעד רקורסייה לבדוק אם צירוף המקדמים כבר מופיע ב-SET. זה עדיין לא מספיק יעיל כדי לפתור את אותו הדבר עבור SUM = 500 אבל זאת התחלה.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
