Advertisement
Guest User

phonebook problem c++

a guest
Jul 13th, 2015
291
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <array>
  3. #include <cstdio>
  4. #include <cmath>
  5.  
  6.  
  7. std::array<int,4> stars_bars(std::array<int,4> parts, int stars, int bars);
  8. void print_parts(std::array<int,4> parts);
  9. int slice_sum(int start, int delta, std::array<int,26> freqs);
  10. int score(std::array<int,4>);
  11.  
  12. std::array<int,26> freqs = {16, 4, 17, 10, 15, 4, 4, 6, 7, 14, 9, 17, 27, 6, 1, 9, 0, 12, 20, 8, 0, 3, 4, 0, 3, 4};
  13.  
  14. int main(int argc, char* argv[]){
  15.   std::array<int,4> parts;
  16.   parts.fill(0);
  17.   //std::cout << slice_sum(4, 6, freqs);
  18.   //std::array<int,4> test = {26, 0, 0, 0};
  19.   print_parts(stars_bars(parts, 26, 4));
  20.   return 0;
  21. }
  22.  
  23.  
  24. void print_parts(std::array<int,4> parts){
  25.   for (int i = 0; i < 4; i++){
  26.     std::cout << parts[i] << " ";
  27.   }
  28.  
  29.   std::cout << std::endl;
  30. }
  31.  
  32. int score(std::array<int,4> parts){
  33.   int score = 0;
  34.   int place = 0;
  35.   for(int i = 0; i < 4; i++){
  36.     score += abs(slice_sum(place, parts[i], freqs) - 55);
  37.     place += parts[i];
  38.   }
  39.   return score;
  40. }
  41.  
  42. int slice_sum(int start, int delta, std::array<int,26> freqs){
  43.   int sum = 0;
  44.   for(int i = 0; i < delta; i++){
  45.     sum += freqs[i + start];
  46.   }
  47.  
  48.   return sum;
  49.  
  50. }
  51.  
  52. /* our recursion function */
  53. std::array<int,4> stars_bars(std::array<int,4> parts, int stars, int bars){
  54.   //declare these static
  55.   //so they persist in spite of recursion
  56.   static int min_score = 330;
  57.   static std::array<int,4> min_volumes = {26,0,0,0};
  58.  
  59.  
  60.   /* exit case 1, last bar. */
  61.   //std::cout << stars << "\t" << bars << std::endl;
  62.   if (bars == 1) {
  63.     parts[0] = stars;
  64.     int sc = score(parts);
  65.     if (sc <= min_score){
  66.       //print_parts(parts);
  67.       min_score = sc;
  68.       min_volumes = parts;
  69.     }
  70.    
  71.     return min_volumes;
  72.  
  73.   }
  74.  
  75.   // /* exit case 2, no more stars. */
  76.   // if (stars == 0){
  77.   //   //std::cout << "exit 2" << std::endl;
  78.   //   //fill the remaining cells with 0
  79.   //   for(int i = 1; i < bars; i++) {
  80.   //     parts[i] = 0;
  81.   //   }
  82.   //   print_parts(parts);
  83.   //   return parts;
  84.  
  85.   // }
  86.  
  87.   //main case
  88.   for(int i = 0; i <= stars; i++) {
  89.     //std::cout << "main case" << std::endl;;
  90.  
  91.     parts[bars-1] = i;
  92.     stars_bars(parts, stars-i, bars-1);
  93.   }
  94.  
  95.  
  96.   //print_parts(min_volumes);
  97.   return min_volumes;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement