home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / vrac / tpchal_1.zip / RB.C < prev    next >
C/C++ Source or Header  |  1994-05-26  |  6KB  |  217 lines
  1. /*********************************************************************
  2.  
  3. Subj: A simple programming challenge
  4.  
  5. The object is to find a particular nine digit decimal number.  The number
  6. must consist of the nine digits (1,2,3...9).  Each (and every) digit is used
  7. once, and only once. The number must have the following properties...
  8.  
  9. The leftmost digit of the number must be evenly divisible by the number 1.
  10. (trivial)
  11.  
  12. The leftmost two digits of the number must be evenly divisible by the number
  13. 2.
  14.  
  15. The leftmost three digits of the number must be evenly divisible by the
  16. number 3, and so on.  The entire number must be evenly divisible by the
  17. number 9.
  18.  
  19. There is only one number which will satisfy the above conditions.
  20.  
  21. *********************************************************************/
  22.  
  23. /*********************************************************************
  24.  
  25. Ron Bemis' (1:124/1113) Solution
  26.  
  27. Interesting problem.
  28.  
  29. Once they learn how to use a computer, it's amazing how many people make it do their thinking for them.  This is (almost) just a simple logic problem.
  30.  
  31. Although you can could use the computer to generate the possible solutions and eliminate duplicate numbers, I found it just as easy to do it with my text editor.
  32.  
  33. o Since 0 cannot be used, #5 must be a 5.
  34.  
  35. o #1 can be 1, 3, 7 or 9.
  36.  
  37. o #2 can be 2, 4, 6 or 8.
  38.  
  39. o #3 can be 3, 5, 7 or 9.
  40.  
  41. o #1-3 must be a multiple of 3.  That gives 20 possibilities:
  42.  
  43.     123     321     723     921
  44.     129     327     729     927
  45.     147     369     741     963
  46.     183     381     783     981
  47.     189     387     789     987
  48.  
  49. o Since #1-4 must be a multiple of 4, #3-4 must also be a multiple of
  50.   4, so #4 must be 2 or 6 (since #3 is odd).
  51.  
  52. o Since #4 is 2 or 6, and #5 is 5, there are only 6 possibilies for
  53.   the #4-6 range:
  54.  
  55.     254     652
  56.     256     654
  57.     258     658
  58.  
  59. o Since #1-6 must be a multiple of 3 as well as 6, and since #1-3 are
  60.   already a multiple of 3, #4-6 must be a multiple of 3.  This leaves
  61.   only three possibilities for #4-6:
  62.  
  63.     258
  64.     654
  65.     658
  66.  
  67. o Since #1-8 must be a multiple of 8 and since #6 is either 4 or 8,
  68.   #7-8 must be a multiple of 8, so #7-8 can be:
  69.  
  70.     16
  71.     32
  72.     72
  73.     96
  74.  
  75. o Since #4 and #8 are assigned 2 and 6, #2 and #6 must be 4 and 8.
  76.  
  77. o Since #2 must be 4 or 8, the possibilies for #1-3 are cut in half:
  78.  
  79.     147     741
  80.     183     783
  81.     189     789
  82.     381     981
  83.     387     987
  84.  
  85. o Combine the possibilities for #1-3 and #4-6:
  86.  
  87.     #1-3        #4-6
  88.     ----        ----
  89.     147         258
  90.     183         654
  91.     189         658
  92.     381
  93.     387
  94.     741
  95.     783
  96.     789
  97.     981
  98.     987
  99.  
  100.     147258          147654 (4)      147658
  101.     183258 (8)      183654          183658 (8)
  102.     189258 (8)      189654          189658 (8)
  103.     381258 (8)      381654          381658 (8)
  104.     387258 (8)      387654          387658 (8)
  105.     741258          741654 (4)      741658
  106.     783258 (8)      783654          783658 (8)
  107.     789258 (8)      789654          789658 (8)
  108.     981258 (8)      981654          981658 (8)
  109.     987258 (8)      987654          987658 (8)
  110.  
  111. o And eliminate repeated 4's and 8's:
  112.  
  113.     147258                          147658
  114.                     183654
  115.                     189654
  116.                     381654
  117.                     387654
  118.     741258                          741658
  119.                     783654
  120.                     789654
  121.                     981654
  122.                     987654
  123.  
  124. o #8 must be 2 or 6 (whichever #4 isn't), and the possibilities for
  125.   #7-8 are limited to 16, 32, 72 and 96.  So if #4 is a 2, #7-8 can be
  126.   16 or 96 and if #4 is a 6, #7-8 can be 32 or 72.
  127.  
  128.     14725816 (1)    14725896
  129.     14765832        14765872 (7)
  130.     18365432 (3)    18365472
  131.     18965432        18965472
  132.     38165432 (3)    38165472
  133.     38765432 (3)    38765472 (7)
  134.     74125816 (1)    74125896
  135.     74165832        74165872 (7)
  136.     78365432 (3)    78365472 (7)
  137.     78965432        78965472 (7)
  138.     98165432        98165472
  139.     98765432        98765472 (7)
  140.  
  141. o And eliminate repeated digits:
  142.  
  143.     14725896
  144.     14765832
  145.     18365472
  146.     18965432
  147.     18965472
  148.     38165472
  149.     74125896
  150.     74165832
  151.     78965432
  152.     98165432
  153.     98165472
  154.     98765432
  155.  
  156. o Using all nine digits once assures us that any number will be a
  157.   multiple of 9, so #9 is whatever is left over.  The 12 possible
  158.   solutions fall neatly into place:
  159.  
  160.     147258963
  161.     147658329
  162.     183654729
  163.     189654327
  164.     189654723
  165.     381654729
  166.     741258963
  167.     741658329
  168.     789654321
  169.     981654327
  170.     981654723
  171.     987654321
  172.  
  173. o These can be checked for divisibility by 7 with a calculator.  :-)
  174.  
  175. *********************************************************************/
  176.  
  177. #include <stdio.h>
  178.  
  179. int main(void)
  180. {
  181.       unsigned long test;
  182.       unsigned long possible[] = {
  183.             147258963L,
  184.             147658329L,
  185.             183654729L,
  186.             189654327L,
  187.             189654723L,
  188.             381654729L,
  189.             741258963L,
  190.             741658329L,
  191.             789654321L,
  192.             981654327L,
  193.             981654723L,
  194.             987654321L
  195.             };
  196.       int i
  197. #ifndef TEST
  198.       ;
  199. #else
  200.       , I;
  201.  
  202.       for (I = 0; I < 1000; ++I)
  203.       {
  204. #endif
  205.             for (i=0; i<sizeof(possible)/sizeof(long); i++)
  206.             {
  207.                   test = possible[i] / 100L;                /* 7 digits */
  208.                   if (test % 7L == 0)
  209.                         printf("%lu\n", possible[i]);
  210.             }
  211.             return(0);
  212. #ifdef TEST
  213.       }
  214. #endif
  215.       return 0;
  216. }
  217.