סכום הפרשי משנה

נסה את זה ב-GfG Practice

#practiceLinkDiv { display: none !חשוב; }

בהינתן קבוצה S המורכבת מ-n מספרים, מצא את סכום ההפרש בין האלמנט האחרון והראשון של כל תת-קבוצה. אנו מוצאים את הרכיב הראשון והאחרון של כל תת-קבוצה על ידי שמירתם באותו סדר כפי שהם מופיעים בקבוצת הקלט S. כלומר sumSetDiff(S) = ? (אחרונים - ראשונים) כאשר הסכום עובר על כל קבוצות המשנה של S.

פֶּתֶק:

רכיבים בתת-הקבוצה צריכים להיות באותו סדר כמו ב-S. דוגמאות:

 S = {5 2 9 6} n = 4   
 Subsets are:   
 {5} last(s)-first(s) = 0.   
 {2} last(s)-first(s) = 0.   
 {9} last(s)-first(s) = 0.   
 {6} last(s)-first(s) = 0.   
 {52} last(s)-first(s) = -3.   
 {59} last(s)-first(s) = 4.   
 {56} last(s)-first(s) = 1.   
 {29} last(s)-first(s) = 7.   
 {26} last(s)-first(s) = 4.   
 {96} last(s)-first(s) = -3.   
 {529} last(s)-first(s) = 4.   
 {526} last(s)-first(s) = 1.   
 {596} last(s)-first(s) = 1.   
 {296} last(s)-first(s) = 4.   
 {5296} last(s)-first(s) = 1.   
 Output = -3+4+1+7+4-3+4+1+1+4+1   
  = 21.   
   מומלץ: נא לפתור את זה ב'   לְתַרְגֵל   תחילה לפני המעבר לפתרון.   
     פתרון פשוט    
   שכן בעיה זו היא למצוא את ההפרש בין האלמנט האחרון והראשון עבור כל תת קבוצה של קבוצה S ולהוציא את הסכום של ll ההבדלים הללו. מורכבות הזמן עבור גישה זו היא O(2  
   ^נ 
   ).  
      פתרון יעיל    
   לפתור את הבעיה במורכבות זמן ליניארית. ניתן לנו קבוצה S המורכבת מ-n מספרים ועלינו לחשב את סכום ההפרש בין האלמנט האחרון והראשון של כל תת-קבוצה של S, כלומר sumSetDiff(S) = ? (אחרונים - ראשונים) כאשר הסכום עובר על כל קבוצות המשנה של S. שווה ערך sumSetDiff(S) = ? (אחרונים) - ? (ראשונים) במילים אחרות נוכל לחשב את סכום האלמנט האחרון של כל תת-קבוצה ואת סכום האלמנט הראשון של כל תת-קבוצה בנפרד ואז לחשב את ההפרש שלהם. נגיד שהאלמנטים של S הם {a1 a2 a3... an}. שימו לב לתצפית הבאה:  
    קבוצות משנה המכילות אלמנט     a1    בתור האלמנט הראשון ניתן להשיג על ידי לקיחת כל תת-קבוצה של {a2 a3... an} ולאחר מכן הכללת a1 לתוכו. מספר תת-קבוצות כאלה יהיה 2  ^n-1 .  
  ניתן להשיג קבוצות משנה המכילות אלמנט a2 כאלמנט הראשון על ידי נטילת כל תת קבוצה של {a3 a4... an} ולאחר מכן הכללת a2 לתוכו. מספר תת-קבוצות כאלה יהיה 2  ^n-2 .  
  ניתן להשיג קבוצות משנה המכילות אלמנט ai כאלמנט הראשון על ידי נטילת כל תת קבוצה של {ai a(i+1)...an} ולאחר מכן הכללת ai לתוכה. מספר תת-קבוצות כאלה יהיה 2  ^n-i .  
   
 
  לכן סכום האלמנט הראשון של כל תת-הקבוצות יהיה: SumF = a1.2  
  ^n-1 
  + a2.2  
  ^n-2 
  +...+ an.1 באופן דומה נוכל לחשב את סכום האלמנט האחרון של כל תת-הקבוצות של S (לוקח בכל שלב ai כאלמנט אחרון במקום אלמנט ראשון ולאחר מכן השגת כל תת-הקבוצות). SumL = a1.1 + a2.2 +...+ an.2  
  ^n-1 
  לבסוף התשובה לבעיה שלנו תהיה  
     SumL - SumF    
  .  
     יישום:    
  C++      // A C++ program to find sum of difference between   // last and first element of each subset   #include       // Returns the sum of first elements of all subsets   int     SumF  (  int     S  []     int     n  )   {      int     sum     =     0  ;      // Compute the SumF as given in the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  S  [  i  ]     *     pow  (  2       n  -  i  -1  ));      return     sum  ;   }   // Returns the sum of last elements of all subsets   int     SumL  (  int     S  []     int     n  )   {      int     sum     =     0  ;      // Compute the SumL as given in the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  S  [  i  ]     *     pow  (  2       i  ));      return     sum  ;   }   // Returns the difference between sum of last elements of   // each subset and the sum of first elements of each subset   int     sumSetDiff  (  int     S  []     int     n  )   {      return     SumL  (  S       n  )     -     SumF  (  S       n  );   }   // Driver program to test above function   int     main  ()   {      int     n     =     4  ;      int     S  []     =     {  5       2       9       6  };      printf  (  '%d  n  '       sumSetDiff  (  S       n  ));      return     0  ;   }   
  Java      // A Java program to find sum of difference    // between last and first element of each    // subset   class   GFG     {          // Returns the sum of first elements       // of all subsets      static     int     SumF  (  int     S  []       int     n  )      {      int     sum     =     0  ;      // Compute the SumF as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *         Math  .  pow  (  2       n     -     i     -     1  ));      return     sum  ;      }      // Returns the sum of last elements       // of all subsets      static     int     SumL  (  int     S  []       int     n  )      {      int     sum     =     0  ;      // Compute the SumL as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *      Math  .  pow  (  2       i  ));          return     sum  ;      }      // Returns the difference between sum       // of last elements of each subset and       // the sum of first elements of each       // subset      static     int     sumSetDiff  (  int     S  []       int     n  )      {      return     SumL  (  S       n  )     -     SumF  (  S       n  );      }      // Driver program      public     static     void     main  (  String     arg  []  )      {      int     n     =     4  ;      int     S  []     =     {     5       2       9       6     };          System  .  out  .  println  (  sumSetDiff  (  S       n  ));      }   }   // This code is contributed by Anant Agarwal.   
  Python3      # Python3 program to find sum of   # difference between last and    # first element of each subset   # Returns the sum of first   # elements of all subsets   def   SumF  (  S     n  ):   sum   =   0   # Compute the SumF as given   # in the above explanation   for   i   in   range  (  n  ):   sum   =   sum   +   (  S  [  i  ]   *   pow  (  2     n   -   i   -   1  ))   return   sum   # Returns the sum of last   # elements of all subsets   def   SumL  (  S     n  ):   sum   =   0   # Compute the SumL as given   # in the above explanation   for   i   in   range  (  n  ):   sum   =   sum   +   (  S  [  i  ]   *   pow  (  2     i  ))   return   sum   # Returns the difference between sum   # of last elements of each subset and   # the sum of first elements of each subset   def   sumSetDiff  (  S     n  ):   return   SumL  (  S     n  )   -   SumF  (  S     n  )   # Driver program   n   =   4   S   =   [  5     2     9     6  ]   print  (  sumSetDiff  (  S     n  ))   # This code is contributed by Anant Agarwal.   
  C#         // A C# program to find sum of difference    // between last and first element of each    // subset   using     System  ;   class     GFG     {          // Returns the sum of first elements       // of all subsets      static     int     SumF  (  int     []  S       int     n  )      {      int     sum     =     0  ;          // Compute the SumF as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *         Math  .  Pow  (  2       n     -     i     -     1  ));      return     sum  ;      }          // Returns the sum of last elements       // of all subsets      static     int     SumL  (  int     []  S       int     n  )      {      int     sum     =     0  ;          // Compute the SumL as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *      Math  .  Pow  (  2       i  ));          return     sum  ;      }          // Returns the difference between sum       // of last elements of each subset and       // the sum of first elements of each       // subset      static     int     sumSetDiff  (  int     []  S       int     n  )      {      return     SumL  (  S       n  )     -     SumF  (  S       n  );      }          // Driver program      public     static     void     Main  ()      {      int     n     =     4  ;      int     []  S     =     {     5       2       9       6     };          Console  .  Write  (  sumSetDiff  (  S       n  ));      }   }       // This code is contributed by nitin mittal.   
  JavaScript      // Returns the sum of first elements of all subsets   function     sumF  (  S       n  )     {      let     sum     =     0  ;      // Compute the SumF as given in the above explanation      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )     {      sum     +=     S  [  i  ]     *     Math  .  pow  (  2       n     -     i     -     1  );      }      return     sum  ;   }   // Returns the sum of last elements of all subsets   function     sumL  (  S       n  )     {      let     sum     =     0  ;      // Compute the SumL as given in the above explanation      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )     {      sum     +=     S  [  i  ]     *     Math  .  pow  (  2       i  );      }      return     sum  ;   }   // Returns the difference between sum of last elements of each subset and the sum of first elements of each subset   function     sumSetDiff  (  S       n  )     {      return     sumL  (  S       n  )     -     sumF  (  S       n  );   }   // Driver program to test the above functions   function     main  ()     {      const     n     =     4  ;      const     S     =     [  5       2       9       6  ];      console  .  log  (  sumSetDiff  (  S       n  ));   }   main  ();   
  PHP         // A PHP program to find sum    // of difference between last    // and first element of each subset   // Returns the sum of first    // elements of all subsets   function   SumF  (   $S     $n  )   {   $sum   =   0  ;   // Compute the SumF as given    // in the above explanation   for   (  $i   =   0  ;   $i    <   $n  ;   $i  ++  )   $sum   =   $sum   +   (  $S  [  $i  ]   *   pow  (  2     $n   -   $i   -   1  ));   return   $sum  ;   }   // Returns the sum of last   // elements of all subsets   function   SumL  (   $S     $n  )   {   $sum   =   0  ;   // Compute the SumL as given   // in the above explanation   for  (  $i   =   0  ;   $i    <   $n  ;   $i  ++  )   $sum   =   $sum   +   (  $S  [  $i  ]   *   pow  (  2     $i  ));   return   $sum  ;   }   // Returns the difference between   // sum of last elements of   // each subset and the sum of   // first elements of each subset   function   sumSetDiff  (   $S     $n  )   {   return   SumL  (  $S     $n  )   -   SumF  (  $S     $n  );   }   // Driver Code   $n   =   4  ;   $S   =   array  (  5     2     9     6  );   echo   sumSetDiff  (  $S     $n  );   // This code is contributed by anuj_67.   ?>   
   
  תְפוּקָה:  
   21   
 
  מורכבות זמן : O(n) מאמר זה נתרם על ידי  
     אקאש אגרוואל    
  . אם אתה אוהב GeeksforGeeks ותרצה לתרום אתה יכול גם לכתוב מאמר באמצעות  
  bijdrage.geeksforgeeks.org  
  או שלח את המאמר שלך בדוא"ל ל[email protected]. ראה את המאמר שלך מופיע בעמוד הראשי של GeeksforGeeks ועזור לגיקים אחרים.  
 
         צור חידון