home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / vrac / tpchal_1.zip / DD_23.TXT < prev    next >
Text File  |  1994-05-22  |  4KB  |  111 lines
  1.  
  2. Date:   Sun May 22 1994  05:51:09
  3. From:   Dave Dunfield
  4. To:     Ray Gardner
  5. Subj:   A simple programming challenge
  6. Attr:   
  7. international C echo           -------------------------------
  8.  RG> Tony, here's a possible solution:
  9.  RG> /* solve.c -- find solution to simple programming challenge
  10.  ... excellent, top-notch algorithm deleted for brevity ...
  11.  
  12. Ray,
  13. You came up with virtually the same recursive algorithm I did, and
  14. you must have posted it earlier since I got it the day I posted
  15. mine. :-(  My only excuse is that I missed the original challange,
  16. and was waiting around for someone to quote it completely.
  17.  
  18. To insure that I contribute something useful to the thread, here are
  19. a couple of interesting variations on my original program (All code
  20. below is hereby donated to the public domain):
  21.  
  22.  
  23. #1 - Here the program has been converted to an iterative solution
  24. (non-recursive):
  25.  
  26. On a system with "expensive" function calls, it could be faster, however
  27. additional division operations to clean up after each attempt are likely
  28. to (more than) negate any speed advantage.
  29.  
  30. Being non-recursive, it will use considerably less stack space.
  31.  
  32. It uses a pre-allocated stack to keep track of the digit attempted at
  33. each position, so that it can properly resume from nested attempts...
  34. This is handled much more nicely in the recursive solution, in which
  35. the stack in inherent in local variable allocation.
  36.  
  37. Use of 'goto' avoids the necessity of an extra test following the
  38. nested for loop, which keeps it closer to the recursive program.
  39.  
  40. #include <stdio.h>
  41. main()
  42. {
  43.     long num = 0L, next;
  44.     int i, n = 1;
  45.     char digits[10] = { 0 };
  46.     char lastdig[10] = { 0 };
  47.  
  48.     do {
  49.     next:
  50.         if(n >= 10)                             /* This number qualifies */
  51.             printf("%ld\n", num);
  52.         else for(i=lastdig[n]+1; i < 10; ++i) { /* Test digits 1-9 only */
  53.             if(digits[i])                       /* Digit in use */
  54.                 continue;
  55.             if(!((next = num*10 + i) % n)) {    /* Divides - proceed */
  56.                 digits[i] = -1;                 /* Mark digit as used */
  57.                 num = next;                     /* Proceed from here */
  58.                 lastdig[n++] = i;               /* Save continuation */
  59.                 goto next; } }                  /* Restart test */
  60.         digits[num % 10] = 0;                   /* Release digit */
  61.         num /= 10;                              /* Remove last attempt */
  62.         lastdig[n] = 0; }                       /* Reset lower starts */
  63.     while(--n);
  64. }
  65.  
  66. #2 - This recursive version has been compressed into a single function
  67. program.
  68.  
  69. It should operate at similar speeds to the original, two "moves" have
  70. been added, as well as an increment and decrement. Parameter passing
  71. and one addition have been removed.
  72.  
  73. It uses less stack space, as the parameters are not passed. On most
  74. systems, this will translate to 6 bytes per recursion (60 total).
  75.  
  76. It is probably one of few functional recursive main() functions
  77. that you will encounter in this echo.
  78.  
  79. #include <stdio.h>
  80. main()
  81. {
  82.     int i;
  83.     long savenum;
  84.     static int n = 0;
  85.     static char digits[10] = { 0 };
  86.     static long num = 0;
  87.  
  88.     ++n;
  89.     if(n >= 10)                             /* This number qualifies */
  90.         printf("%ld\n", num);
  91.     else for(i=1; i < 10; ++i) {            /* Test digits 1-9 only */
  92.         if(digits[i])                       /* Digit in use */
  93.             continue;
  94.         savenum = num;                      /* Save our place */
  95.         if(!((num = num*10 + i) % n)) {     /* Divides - proceed */
  96.             digits[i] = -1;                 /* Mark digit as used */
  97.             main();                         /* Try sub-combinations */
  98.             digits[i] = 0; }                /* Release digit */
  99.         num = savenum; }                    /* Restore place */
  100.     --n;
  101. }
  102.  
  103. Regards,
  104.  
  105. Dave
  106.  
  107. --- Squed 1.07
  108.  * Origin: Dunfield Development Systems - 613-256-5820 (1:163/107.4)
  109.  
  110.  
  111.