נושא: חידות

נשלח בתאריך: 27 August 2007 בשעה 18:02 | IP רשוּם

הכותרת של הפורום היא תיכנות,חידות,ושאלות.

תיכנות יש והרבה.
שאלות לא חסר.
חידות קצת פחות...

אז אני פותח שירשור לחידות מעניינות שיגרמו לגלגלים להסתובב.
בשביל להתחיל ברגל ימין 2 חידות ראשונות:

1. נתונה מחרוזת מילים המורכבת מאותיות ומספרים, בהינתן מחרוזת כזו יש להפוך
   את כל המילים בה לפי הסדר. אילוצים: הפתרון חייב להיות יעיל ביותר. 
   לדוגמה: המחרוזת: UNDER WAR ROCKS
            תתקבל:    REDNU RAW SKCOR

2. נתון עץ, כתוב תוכנית איטרטיבית המדפיסה את תוכן העץ לפי רמותיו מהנמוכה לגבוה.
    לדוגמה:                    ;   1
                                  \  /      
                                3     2
                                  /   \  /
                                   7 6   8
   יודפס: 8,7,6,2,3,1

  

נשלח בתאריך: 03 September 2007 בשעה 18:23 | IP רשוּם

יפה מאוד אורח!!!

כל הכבוד.

נשלח בתאריך: 03 September 2007 בשעה 19:50 | IP רשוּם

זה נכון, מס' שהוא חזקה של 2 בייצוג בינארי הוא בעל 1 יחידי.

אבל השאלה היא לספק אלגוריתם יעיל שמחזיר אמת או שקר אם המס' הוא חזקה של 2.

נשלח בתאריך: 03 September 2007 בשעה 22:46 | IP רשוּם

יפה מאד!!!

הפתרון בשפת C לדוגמה:

נשלח בתאריך: 04 September 2007 בשעה 18:24 | IP רשוּם

לא ידעתי שהחידה כבר כאן,

הפתרון שלי הוא אותו פתרון כלומר, להריץ בלולאה שני מצביעים שאחד קופץ מס' זוגי של
צמתים והשני מס' איזוגי של צמתים.
אם הרשימה היא מעגלית מובטח לנו שהם יפגשו מתישהו (הוכחה ע"י אינדוקציה מתמטית)
אחרת אם הרשימה איננה מעגלית אז המצביע שמדלג מהר יותר יגיע לסוף הרשימה ולכן היא איננה מעגלית.

 יפה צחי.

נשלח בתאריך: 05 September 2007 בשעה 13:24 | IP רשוּם

אם יש איבר שחוזר יותר מפעם אחת, לא ניתן בוודאות לעשות זאת ב-(O(log n

תחשבו על מערך שנראה כך:

1 , 0 , 0 , ... , 0 , 0

הוא ממויין אבל לאחר הזזה הוא יראה למשל כך:

0, 0 , ... , 0 , 1 , 0 , 0, 0, 0 , ... , 0 , 0

אם מחפשים את האיבר 1 , אזי כל חיפוש ב-( O(log n

לא ימצא בוודאות את האיבר. תמקד את השאלה למערך ממויין שכל האיברים בו הם ייחודיים.

ד"א, תודה על הקרדיט

נשלח בתאריך: 06 September 2007 בשעה 00:44 | IP רשוּם

צחי תודה...

שכחתי לציין שכמובן שהאיברים חייבים להיות שונים זה מזה.

שושן,לגבי התוכנית ששלחת המשפט הבא יחזיר את האינדקס הימני ביותר
לפי הדוגמה שנתתי בשאלה, וכאמור זה לא האמצע:

דבר שני לא הבנתי איך אתה מחליט איפה לחפש אחרי מצאת את את האמצע.

נשלח בתאריך: 06 September 2007 בשעה 00:51 | IP רשוּם

למי שמתקשה עם השאלה הקודמת ניתן עוד שאלה פשוטה יותר:

כתוב תוכנית המקבלת מס' טיבעי כלשהו ומדפיסה את כל האיברים הראשוניים מ-0 ועד אליו.
אילוצים: אין להשתמש בחילוק.

נשלח בתאריך: 06 September 2007 בשעה 01:37 | IP רשוּם

יפה זה פתרון טוב בהנחה שאתה מוצא את אינדקס ההזזה בזמן של (O(LOG n

אלגוריתם:
1.מצא אינדקס(A). 
2.חיפוש בינארי משמאל לאינדקס(A). 
3.חיפוש בינארי מימין לאינדקס(A).
4.החזר תשובה.

צעד 1: (O(LOG n
צעד 2: (O(LOG n
צעד 3: (O(LOG n

סה"כ אלגוריתם בזמן של (O(LOG n (דרך אגב עובד גם כאשר ישנם איברים דומים). 

אבל...
כל זה טוב ויפה בתנאי שאתה כותב אלגוריתם שמוצא את האינדקס ב-(O(LOG n,
לכן בשביל שהפתרון יהיה מלא עליך לספק אלגוריתם כזה.  

(אגב, ישנו פתרון אחר שעובד בזמן של (O(LOG n בתנאי שהאיברים שונים זה מזה.)

נשלח בתאריך: 07 September 2007 בשעה 00:49 | IP רשוּם

כלומר בסופו של דבר אתה מסתכל על טווחים ומסיק איפה האמצע על פיהם כאשר האיברים שונים זה מזה.

הפתרון שנתת די קרוב לפתרון שאני מכיר לשאלה, גם הוא פועל על סמך ההנחות שאתה הצגת
ועובד רק כאשר האיברים שונים אחד מן השני. כיוון שהפתרון שלך די דומה אני אציג את
הפתרון שאני מכיר לשאלה:

הרעיון בגדול הוא להסתכל על טווחים.
כיוון שהמערך מוזז אם נסתכל על טווח מסוים שני דברים יאמרו לנו אם האיבר אותו אנו מחפשים נמצא בתחום:
אם הקצה השמאלי של התחום קטן מן המס' אותו אנו מחפשים והקצה השמאלי קטן מן הקצה הימני.
או שהקצה השמאלי גדול מן הקצה הימני והקצה הימני גדול מן המס' אותו אנו מחפשים.

בשביל חיפוש בזמן של (O(LOG n נבצע חילוק של המערך לשני חלקים שווים (פחות או יותר), נבדוק את התנאים לעיל ונמשיך לחלק באופן רקורסיבי.
הפתרון כמובן יעבוד אך ורק אם האיברים שונים אחד מן השני.

בכל מקרה כל הכבוד שושן

נשלח בתאריך: 07 September 2007 בשעה 01:24 | IP רשוּם

שאלה שנאבדה בין הפתרונות:

1.כתוב תוכנית המקבלת מס' טיבעי כלשהו ומדפיסה את כל האיברים הראשוניים מ-0 ועד אליו.
אילוצים: אין להשתמש בחילוק.

חבר'ה זרקו גם אתם משהו...

נשלח בתאריך: 12 September 2007 בשעה 06:39 | IP רשוּם

נו מה עם פתרון?

נשלח בתאריך: 12 September 2007 בשעה 15:02 | IP רשוּם

זה לא מדוייק כלכך כי לפי מה שאתה אומר אתה אמור לדעת את כל המס' הראשוניים בין 1 לשורש המס' הנתון.
מה אם זה מס' גדול מאד? לדוגמה 10000 שורשו 100 ומס' ראשוניים מ-1 עד 100 לא ידועים לכולם.

ההנפה של ארטוסתנס היא שיטת אלמינציה שמורידה כפולות של מספרים החל מ-2 ועד
לשורש המס' המבוקש.
לדוגמה: n = 25.

יוצרים מערך 1..25.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

מוחקים כפולות של 2.
1 3 5 7 9 11 13 15 17 19 21 23 25

לאחר מכן המס' הבא במערך הוא 3 לכן מוחקים את כל הכפולות שלו.
1 3 5 7 11 13 17 19 23 25

לאחר מכן המס' הבא הוא 5 שהוא גם שורש של 25 מוחקים את הכפולות שלו וסיימנו.
1 3 5 7 11 13 17 19 23.

קיבלנו את כל המס' הראשוניים מ-1 עד 25 ללא צורך בידע מי המס' הראשוניים מ-1 עד 5.

נשלח בתאריך: 12 September 2007 בשעה 18:10 | IP רשוּם

פתרון: לדוגמה כאשר 6 = n.

ניתן לפרק את המטריצה לשתי מטריצות  A ו- B כאשר חיבורן יתן את המטריצה המבוקשת.

המטריצה A:

36  36  36  36  36  36

16  16  16  16  16  36

16  04  04  04  16  36

16  04  00  04  16  36

16  04  04  04  16  36

16  16  16  16  16  36

והמטריצה B:

-1      -2      -3      -4      -5      -6

0       -1      -2      -3      -4      -7

1       0       -1      -2      -5      -8

2       1       0       -3      -6      -9

3       2       3       4       -7      -10

4       5       6       7       8       -11

כמו כן ידועים לנו מראש הקוארדינטות (אינדקסים) של כל איבר ואיבר במטריצה המבוקשת בצורה הבאה:

(0,0)    (1,0)    (2,0)    (3,0)    (4,0)

(0,1)    (1,1)    (2,1)    (3,1)    (4,1)

(0,2)    (1,2)    (2,2)    (3,2)    (4,2)

(0,3)    (1,3)    (2,3)    (3,3)    (4,3)

המטריצה A:

אם נתבונן במטריצה A נוכל לראות שהשורה הראשונה והעמודה האחרונה מורכבות מאיברים
השווים ל-N. אם נוריד שורה ועמודה זו נקבל את המטריצה הבאה:

16  16  16  16  16 

16  04  04  04  16 

16  04  00  04  16 

16  04  04  04  16  
16  16  16  16  16

במטריצה שהתקבלה ניתן לראות מעין "טבעות" המקיימות באופן דומה את אותה החוקיות כאשר כל איבר בטבעת מתקבל ע"י הריבוע של (מס' הטבעת * 2 – N).
כלומר, האיבר בטבעת החיצונית ביותר במטריצה הוא , בטבעת הפנימית הבאה  וכן הלאה עד 0.

מכאן שאפשרי לכתוב נוסחה מתמטית שתתן לנו כל איבר במטריצה A עפ"י הכללים לעיל ובהסתמך על קוארדינטות כל איבר.
למען פישוט הנוסחה נוציא שורש מכל איבר במטריצה A ונקבל את המטריצה הבאה:

6       6       6       6       6       6

4       4       4       4       4       6

4       2       2       2       4       6

4       2       0       2       4       6

4       2       2       2       4       6

4       4       4       4       4       6

הנוסחה הבאה תחזיר כל איבר במטריצה זו לפי הקוארדינטות שלו:

F(x,y) = N – 2 * MIN (x+1, y, N - x+1, N-y)

לדוגמה: הקוארדינטות לאיבר 0 במטריצה הן (2,3) הצבתן בנוסחה תיתן:

F(2,3) = 6 – 2 * MIN (3, 3, 3, 3)  = 6 – 2 * 3 = 0

כל מה שנותר הוא לעלות בריבוע את תוצאת הנוסחה וכך לבנות את המטריצה A.

המטריצה B:

אם נתבונן במטריצה B לאחר שנוריד את העמודה האחרונה והשורה הראשונה נקבל:

0      -1      -2      -3      -4

1       0      -1      -2      -5

2       1       0      -3      -6

3        2       3       4      -7

4        5       6       7       8

נשים לב שמטריצה זו היא מעין מטריצה סימטרית סביב האלכסון כאשר האיברים מעל האלכסון שליליים ומתחתיו חיוביים.
לכן אין צורך לכתוב נוסחה לכל האיברים אלא רק לאיברים שמתחת לאלכסון ולאלכסון עצמו.

0

1       0

2       1       0

3       2       3       4

4       5       6       7       8

(נשים לב: y גדול שווה בערכו ל – x בחלק התחתון כולל האלכסון.)

הכללים לנוסחה ואופן החישוב:

(הקוארדינטות מתייחסות למטריצה המקורית B).

1.איברים שחיבור הקוארדינטות שלהםx+y  קטן שווה מ-N מתקבלים ע"י חישוב פשוט: y – x - 1

לדוגמה: הקוארדינטות של האיבר 2 הם (0,3) לכן נקבל 2 = 3-0-1.

2.איברים שחיבור הקוארדינטות שלהםx+y  גדול מ-N מתקבלים ע"י החישוב:

U(x,y) = ((x+y) – ((N – y)*2)) + 1

לדוגמה: הקוארדינטות של האיבר 6 הם (2,5) לכן נקבל:

  7 – 2 + 1 = 6= U(2,5) = ((2+5) – ((6 – 5)*2)) + 1

3.איברי החלק העליון יכולים להתקבל מאותה נוסחה ע"י סידור הקוארדינטות הצבה והכפלה ב- 1-.

4.איברי השורה העליונה והעמודה האחרונה במטריצה המקורית  Bיחושבו באופן נפרד כך:

 (-1)*(x+y) – 1

לדוגמה קוארדינטות האיבר 11- במטריצה B הן (5,5) הצבה תתן:

(-1)*(5+5) – 1 = -11

פתרון בשפת C:

פונקצית חישוב מינימום בין 2 איברים:

int minimum(int i, int j)

{

  if (i < j) return i; else return j;

}

פונקציה לחישוב המטריצה A:

int A(int i, int j, int Size)

{

  int v = Size- 2*minimum(minimum(i+1,j),minimum(Size-(i+1),Size-j));

    return v*v;

}

פונקציה לחישוב המטריצה B:

int B(int i, int j, int Size)

{

  if (j == 0 || i == Size - 1) // האם האיבר בשורה הראשונה או בעמודה האחרונה לפי 4                    

      return (-1 * (i + j) -1);

  if (j > i)                  בדיקה האם באלכסון התחתון  //

      if (j + i < Size)        //    לפי 2N-בדיקה האם סכום הקוארדינטות קטן מ

        return (j - i - 1);

      else

        return ((j + i) - (Size - j) * 2 + 1);

  else return (-1 * B(j - 1, i + 1, Size)); // לא באלכסון התחתון

סידור הקוארדינטות הכפלה במינוס 1 וקריאה רקורסיבית //                                                                                 

}

קובץ MAIN:

#define N 6

void main()

{

  for (int j = 0;j < N; j++)

  {

      for (int i = 0; i < N; i++)

        cout<<A(i,j,N) + B(i,j,N)<<" ";  

      cout<<endl;

  }

}

נשלח בתאריך: 20 September 2007 בשעה 11:16 | IP רשוּם

נתקלתי לאחרונה בבעיה הנ"ל (בעיה אמיתית - לא תרגיל):

נתון מערך A של n מספרים. המספרים [A[i ו-[A[j נחשבים כצמד אם הם עומדים

ביחס C כלשהו, כלומר אם ([C(A[i],A[j הוא אמת. את ערכו של C ניתן לחשב

בזמן (O(1.

האם קיים אלגוריתם בעל זמן ריצה פולינומיאלי למציאת מספר מקסימלי של צמדים העומדים ביחס C, כאשר כל מספר יכול להשתתף בצמד אחד לכל היותר ?

יש לי השערות בנושא אבל עדיין לא הצלחתי להראות בוודאות שהן נכונות.

כל מחשבה תתקבל בברכה.

נשלח בתאריך: 20 September 2007 בשעה 16:09 | IP רשוּם

פתרון טוב לדעתי יהיה:

- נבנה גרף מכוון כאשר בין a ל-b קיימת קשת אם ורק אם (C(a,b מתקיים.
- נבחר מבין הקודקודים קודקוד v שדרגת היציאה שלו היא מינימלית אך גדולה מ-0.
- מבין הקודקודים שקיימת אליהם קשת מקודקוד v נבחר קודקוד u כך שדרגת הכניסה שלו היא מינימלית.
- נוציא קודקודים אלה כזוג (v,u), נבנה גרף חדש ונחזור על פעולות אלה עד אשר לא נותרו זוגות אפשריים.

אם מסתכלים על גרף מכוון במבנה של מטריצת שכנות אזי:

צעד 1: (O(n^2 
צעד 2: (O(n^2
צעד 3: (O(n^2
צעד 4: (O(n (ניתן פשוט למחוק את השורה ועמודה של כל קודקוד שמוציאים).

צעדים 1-4 מתבצעים לכל היותר n פעמים, לכן סה"כ אלגוריתם שניתן לבנות בהסתמך על
פעולות אלה הוא בזמן של (O(n^3.

פתרון בשפת ++C:

bool C(int a,int b){

      // The relation a >= b AND a - b > 2.

      return ((a >= b) && (a - b > 2));

}

void BuildGraphMat(bool B[][10] , int A[], int size){

      for (int i = 0; i < 10; i++)

            for (int j = 0; j < 10; j++)

                  B[j] = C(A,A[j]);

}

int FindMinOutDegree(bool B[][10], int size){

      // Maximun out degree of a given vertex v, should be n-1 at the most.

      int degree = size - 1;

      int index = -1;

      for (int i = 0; i < 10; i++)

      {

            int count = 0;

            for (int j = 0; j < 10; j++)

                  if (B[j]) count++;

            if (count > 0 && count <= degree)

            {

                  degree = count;

                  index = i;

            }

      }

      return index;

}

int FindMinInDegree(bool B[][10], int vertex, int size){

      // Maximun in degree of a given vertex v, should  also be n-1 at the most.

      int degree = size - 1;

      int index = -1;

      for (int i = 0; i < size; i++)

      {

            if (B[vertex])

            {

                  int count = 0;

                  for (int j = 0; j < size; j++)

                         if (B[j]) count++;

                  if (count <= degree)

                  {

                         degree = count;

                         index = i;

                  }

            }

      }

      return index;

}

void RemoveFromGraphMat(bool B[][10], int index, int size){

      for (int i = 0; i < size; i++)

      {

            B[index] = false;

            B[index] = false;

      }

}

void PrintAllCouples(bool B[][10] , int A[], int size){

      int i = FindMinOutDegree(B,10);

      int j = FindMinInDegree(B,i,10);

      while(j != -1 && i!= -1)

      {

            cout<<"("<<A<<","<<A[j]<<") ";

            RemoveFromGraphMat(B,i,10);

            RemoveFromGraphMat(B,j,10);

            i = FindMinOutDegree(B,10);

            j = FindMinInDegree(B,i,10);

      }

}

void main(){

      int A[10] = {-6, 31, 2, 10, -17, 6, 7, -3, 33, 10};

      bool B[10][10];

      BuildGraphMat(B,A,10);

      PrintAllCouples(B,A,10);

{

נשלח בתאריך: 20 September 2007 בשעה 16:12 | IP רשוּם

האם האלגוריתם הזה מבטיח שלכל מערך של n מספרים יימצא תמיד מספר הצמדים המקסימלי האפשרי ?

נשלח בתאריך: 20 September 2007 בשעה 16:15 | IP רשוּם

לא יודע למה אבל הקוד טיפה שונה בשליחה, אז אני אשלח אותו שוב כקוד.

נשלח בתאריך: 20 September 2007 בשעה 16:44 | IP רשוּם

תראה זה סה"כ רעיון שחשבתי עליו אינטואיטיבית, כמובן שצריך להוכיח אותו באינדוקציה
מתמטית לכל מערך בגודל אפשרי, ולכל יחס אפשרי. אבל אין לי כח לזה...
אני לא הצלחתי למצוא אחד ששולל את הרעיון אז בוא תנסה אתה.

עוד שתי הערות לגבי התוכנית:
1. צריך לשלול התייחסות של איבר לעצמו.
2. צריך לתת ערך שלילי לכל אברי המטריצה B לפני בנייתה.

לכן תיקון פונקציית הבניה:

נשלח בתאריך: 20 September 2007 בשעה 16:59 | IP רשוּם

האינטואיציה שלי לגבי פתרון דומה לשלך, למעט העובדה שבאלגוריתם שלי אני מחלק דירוג לכל הקשתות לפי סכום הדרגות של הקדקודים שלהן, ולפי הדירוג הזה אני בוחר איזה קשת להוציא, מחשב את הדירוג החדש וכו'.

למרות זאת, אני לא מרגיש עדיין טוב עם הפתרון הזה, הוא יותר מדי חמדן לטעמי ולכן ללא הוכחה שהוא תמיד מוצא את מקסימום הצמדים ללא תלות בתוכן המערך אני לא מרגיש בטוח להשתמש בו. הפתרון שאני מחפש חייב להיות נכון ב-100% מהמקרים.

אגב, היחס C הוא חסר משמעות לצורך הוכחה, הוכחה יכולה להתבסס על המבנה של הגרף בלבד, כל יחס C משרה מבנה אחר.

אני כרגע בשלב של לנסות לראות אם קיים גרף שעבורו האלגוריתם שוגה - כלומר לא מוצא את מס' הצמדים המקסימלי.

נשלח בתאריך: 20 September 2007 בשעה 19:09 | IP רשוּם

למה אתה צריך את זה בכלל?

כלומר, שתף אותנו...

נשלח בתאריך: 24 September 2007 בשעה 15:45 | IP רשוּם

שלום,

השאלה ששאלת חמציר הינה בעיית "NP-Complete" הקלאסית ביותר שיש, ולכן ל-N גדול, אין לה תשובה יעילה (או לפחות לא מצאו ב-10 שנים האחרונות).

נשלח בתאריך: 24 September 2007 בשעה 16:45 | IP רשוּם

ולוסט תודה אני יודע,

ישנו פתרון לא יעיל המתאים ל-N-ים קטנים (יחסית) אותו אני מבקש.
כמובן שלא דרשתי יעילות בפתרון.

נשלח בתאריך: 24 September 2007 בשעה 16:53 | IP רשוּם

כתבתי תשובה לשאלה השניה ב C# אך גם הוא לא יעיל ל N גדול (אולי עוד NP?):

נשלח בתאריך: 24 September 2007 בשעה 17:31 | IP רשוּם

תודה שושן , באמת חששתי שה ref לא הכרחי אבל מה לעשות אני חדש בC#.

בכל זאת, אם הייתי רוצה להוציא את התשובה כפלט ישירות מהפונקציה לא הייתי צריך להשתמש ברשימת allSubs בכלל, אבל בחרתי לשמור את הנתונים ע"מ שיהיה קל לבצע איתם עוד פעולות אם רוצים. אני ישמח לראות אם מישהו מצא פתרון ל N גדול.

נשלח בתאריך: 24 September 2007 בשעה 21:32 | IP רשוּם

רק בשביל הסדר הטוב: הבעיה היא למצוא את כל תתי הקבוצות של קב' המספרים, כפי שניתן לראות, מס' תתי הקבוצות של קב' בגודל n הוא אקספוננציאלי ביחס ל-n, ולכן כל אלגוריתם שמדפיס את כל תתי הקבוצות, מבצע בהכרח לפחות מס' אקספוננציאלי של צעדים ולכן בוודאות אינו פולינומיאלי ובפרט אינו NP complete. הוא למעשה שייך למחלקה EXP.

נשלח בתאריך: 24 September 2007 בשעה 23:05 | IP רשוּם

כתבתי קוד לשאלת הספירלה שנשאלה פה קודם לכן:

תוכנית זאת מצרפת את המספרים ההולכים וקטנים מ-N למטריצה בסדר נגדי לכיוון הספירלה (פנימה במקום החוצה) דרך פונקציה ריקורסיבית ומדפיסה את המטריצה. זה אפשרי לשחק מעט עם הפרמטרים של הפונקציה כך שיהיה אפשר ליצור ספירלה בעלת שני מימדים שונים זה מזה, אך כמובן שמכפלתם תמיד יהיה חייב להיות שווה ל-N.

נשלח בתאריך: 24 September 2007 בשעה 23:10 | IP רשוּם

בראש ובראשונה צחי צודק, 
כלומר כיוון שמס' תתי הקבוצות לקבוצה נתונה היא אקספוננציאלית, (שתיים בחזקת N
בדיוק), וכיוון שאין דרך להדפיס את הקבוצות מבלי ליצור אותם שידועה לי, הסיבוכיות הטובה
ביותר שניתן להשיג היא אקספוננציאלית.
בכל מקרה כל הכבוד לך .
 
עוד פתרון טיפה שונה:

ניתן לקבוע באופן בינארי מי מהאיברים נמצא בקבוצה ומי לא עפ"י עקרון קוד גריי,
קוד בינארי זה מתנהג בצורה בה בין כל שני אברים ברצף יש שינוי של ביט אחד לכל היותר.
(ניתן לקרוא עליו כאן -[URL=http://he.wikipedia.org/wiki/%D7%A7%D7%95%D7%93_%D7%92%D7%A8%D7%99%D7%99]קוד גריי[/URL).


כעץ ניקח לדוגמה 3 = n תתי הקבוצות הם:
, , , , , , ,  .
אם נתבונן היטב בתתי הקבוצות מימין לשמאל בסדר זה, נוכל לראות כי מקבוצה לקבוצה
האיברים משתנים ע"י הוצאה או הכנסה של איבר אחד בדיוק.
אם נסתכל על סדרת האיברים שמוכנסים או יוצאים מהקבוצה נקבל את הסדרה
הבאה: 1 2 1 3 1 2 1 אחרי זמן מה ניתן לזהות חוקיות רקורסיבית האומרת:

(T(n+1) = T(n),n+1,T(n
T(1) = 1

כעת ניתן לבנות אלגוריתם שבנוי על עקרון זה ומטפל ביצירת הקבוצות ע"י הכנסה והוצאה של איבר אחד בדיוק בכל איטרציה.
האלגוריתם יניב פתרון איטרטיבי בהנחה שסדרת האיברים שיש להכניס ולהוציא מהקבוצה
ידועה לנו מראש וזמן הדפסת הקבוצה זניח.

אלגוריתם:
1.צור את סדרת המספרים. 
2.הדפס קבוצה ריקה.
3.בעבור כל איבר מסדרת האיברים בצע:
  1.3 אם האיבר לא מופיע בקבוצה הכנס אותו לקבוצה אחרת הוצא אותו מהקבוצה.
  2.3 הדפס קבוצה נוכחית.

סיבוכיות:
יצירת סדרת המספרים - שתיים בחזקת N.
כמות האיטרציות המינימלית הנדרשת היא כגודל הסדרה פחות הקבוצה הריקה כלומר -
1 - שתיים בחזקת N. 
סה"כ אלגוריתם (לא יעיל) ב- (O(2^N.

 
מחלקה הממשת רעיון זה ב-CPP:

נשלח בתאריך: 20 February 2008 בשעה 18:39 | IP רשוּם

לא הבנתי- אתה רוצה שנקלוט מחרוזת ונדפיס את המחרוזת שבין כל זוג אותיות צמודות ישנו רווח?

(אולי זה בגלל שאני לא יודע תכנות- אבל לא הבנת)