SHARE
TWEET

Ex4- Backtraking

Alx09 Jun 1st, 2020 (edited) 568 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define natural unsigned short
  5. #define maxN 10000
  6. unsigned v[maxN], n;
  7. static char st[] = { 0, 0, 0, 1, 1, 1, 1};
  8. natural m, p, q;
  9. void Init(natural k) {
  10.     v[k] = 0;
  11. }
  12. natural Succesor(natural k) {
  13.     if (v[k] < 6) {
  14.         v[k]++;
  15.         return 1;
  16.     }
  17.     return 0;
  18. }
  19.  
  20. natural Valid(natural k) {
  21.     natural i;
  22.     for (i = 1; i < k; i++)
  23.         if (v[i] == v[k])
  24.             return 0;
  25.     return 1;
  26. }
  27.  
  28.  
  29. natural Solution(natural k) {
  30.     return (k == n);
  31. }
  32.  
  33. void Print() {
  34.     natural i;
  35.  
  36.     for (i = 1; i <= 6; i++)
  37.         printf("%d", st[v[i]]);
  38.  
  39.     printf("\n");
  40. }
  41.  
  42. void Back() {
  43.     natural k = 1, isS, isV;
  44.     Init(k);
  45.     while (k > 0) {
  46.         isS = 0; isV = 0;
  47.         if (k <= n)
  48.             do {
  49.                 isS = Succesor(k);
  50.                 if (isS) isV = Valid(k);
  51.             } while (isS && !isV);
  52.             if (isS)
  53.                 if (Solution(k))
  54.                     Print();
  55.                 else {
  56.                     k++;
  57.                     Init(k);
  58.                 }
  59.             else
  60.                 k--;
  61.     }
  62. }
  63.  
  64. int main() {
  65.     n = 6;
  66.     Back();
  67.     system("pause");
  68.     return 0;
  69.  
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top