OnLive/DirectX11/C#/.NET/and more…

Project Euler problem 88~
c#

  1:     class Program
  2:     {
  3:         static void Main(string[] args)
  4:         {
  5:             Console.WriteLine("The sum of all the minimal product-sum numbers for 2≤k≤12000: ");
  6: 
  7:             //TestBenchSetup();
  8:             //TestBenchLoader(brute_force_by_generate_and_test_multiplicative_partitions);
  9:             brute_force_by_generate_and_test_multiplicative_partitions();
 10: 
 11:             Console.WriteLine("Press any key to exit");
 12:             Console.ReadKey();
 13:         }
 14: 
 15:         /// <summary>
 16:         /// since the number cannot be lower or same as k, and the num which is(2*k) would always satisfy k
 17:         /// for example: k=3, n=2*k=6, which in turns 1*2*3=6=1+2+3. so the number to test can be limited to k+1 to 2k
 18:         /// the next step is to generate and test all the multiplicative partitions to see if the product-sum condition satisfied
 19:         /// using the method test_product_sum
 20:         /// really slow, but orwill
 21:         /// </summary>
 22:         static int brute_force_by_generate_and_test_multiplicative_partitions()
 23:         {
 24:             var k_range = 12000;
 25:             var k = 2;
 26:             var len = k_range * 2 + 1;
 27:             var map = new int[len];
 28:             while (k <= k_range)
 29:             {
 30:                 var bound = k * 2;
 31:                 for (int num = k + 1; num <= bound; num++)
 32:                 {
 33:                     if (test_product_sum(num, 0, 0, num, k) == true)
 34:                     {
 35:                         map[num]++;
 36:                         break;
 37:                     }
 38:                 }
 39:                 k++;
 40:             }
 41:             var result = 0;
 42:             for (int i = 0; i < len; i++)
 43:             {
 44:                 if (map[i] != 0)
 45:                     result += i;
 46:             }
 47:             return result;
 48:         }
 49: 
 50:         /// <summary>
 51:         /// basically generate all the multiplicative partitions and return true for first one found hat matched the problem's
 52:         /// condition. return false if none to be found
 53:         /// </summary>
 54:         static bool test_product_sum(int num, int divisor_sum, int divisor_count, int number_to_test, int k)
 55:         {
 56:             var bound = num / 2;
 57:             var rem = 0;
 58:             var quotient = 0;
 59:             for (int divisor = 2; divisor <= bound; divisor++)
 60:             {
 61:                 quotient = Math.DivRem(num, divisor, out rem);
 62:                 if (rem == 0)
 63:                 {
 64:                     var local_sum = divisor_sum + divisor;
 65:                     var local_count = divisor_count + 1;
 66: 
 67:                     var total_sum = local_sum + quotient;
 68:                     var total_count = local_count + 1;
 69: 
 70:                     if ((total_count == k && total_sum == number_to_test) || (number_to_test - total_sum == k - total_count))
 71:                         return true;
 72: 
 73:                     if (test_product_sum(quotient, local_sum, local_count, number_to_test, k) == true)
 74:                         return true;
 75:                 }
 76:             }
 77:             return false;
 78:         }
 79: 
 80:         static Stopwatch stopwatch = new Stopwatch();
 81:         static void TestBenchSetup()
 82:         {
 83:             // Uses the second Core or Processor for the Test
 84:             Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
 85:             // Prevents "Normal" processes from interrupting Threads
 86:             Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
 87:             // Prevents "Normal" Threads from interrupting this thread
 88:             Thread.CurrentThread.Priority = ThreadPriority.Highest;
 89:         }
 90:         // see http://www.codeproject.com/KB/testing/stopwatch-measure-precise.aspx
 91:         static void TestBenchLoader(Func<int> test_method)
 92:         {
 93:             stopwatch.Reset();
 94:             stopwatch.Start();
 95:             var result = 0;
 96:             long avg_tick = 0;
 97:             long avg_ms = 0;
 98:             while (stopwatch.ElapsedMilliseconds < 1200)  // A Warmup of 1000-1500 ms 
 99:             // stabilizes the CPU cache and pipeline.
100:             {
101:                 result = test_method(); // Warmup
102:             }
103:             stopwatch.Stop();
104:             for (int repeat = 0; repeat < 20; ++repeat)
105:             {
106:                 stopwatch.Reset();
107:                 stopwatch.Start();
108:                 result = test_method();
109:                 stopwatch.Stop();
110:                 avg_tick += stopwatch.ElapsedTicks;
111:                 avg_ms += stopwatch.ElapsedMilliseconds;
112:             }
113:             avg_tick = avg_tick / 20;
114:             avg_ms = avg_ms / 20;
115:             Console.WriteLine(string.Format("{0} way(ticks:{1}, ms:{2}) Ans:{3}",
116:                 test_method.Method.Name.Replace('_', ' '), avg_tick, avg_ms, result));
117:         }
118:     }

c++

Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s