Перебор чисел

From

Dmitriy Gerasimenko ()

To

Luniov Ruslan

Date

2002-07-19T14:11:30Z

Area

RU.ALGORITHMS

From: "Dmitriy Gerasimenko" <gerasimenko@karelia.ru>



Привет, All!

И спросил у меня радиотехник: "....нужно код разгадать у магнитолки....
цифери я узнал, нужно сделать перебор."
Спрошено - сделано, причём с удовольствием.
Код 4-ёх значный = 2514. N= 4
Вложенные циклы отпадают, т.к. чем больше N тем больше гемор....
Следовательно нужно использовать
алгоритм с возвратом, наподобии "нахождение количества позиций N ферзей на
доска АхВ когда они не бьют друг-друга".
(кстати есть на моём сайте:
http://www.sampo.ru/~gerasimenko/FTP/ferz_exe.zip)

Привожу код на С (Borlabd C++ 3.1 for DOS), который возможно и лучше можно
было сделать, а ? или нельзя ?

#include <dir.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <process.h>
#include <string.h>
#include <ctype.h>

enum TOperator {PRINT, NEXT_SYMBOL, NEXT_POSITION};
char *sOperation[]= {"PRINT", "NEXT_SYMBOL", "NEXT_POSITION"};

int main(int c, char **argv)
{
  char *bytes;
  char *pbytes;
  char *pargv;
  char *trigger;
  char filename[MAXPATH];
  TOperator op;
  int position;
  int count_position;
  FILE *stream;
  unsigned long count;
  //--------------------------------------------------------------
  if (c <= 1) {
    fprintf(stderr, "\nBad command line argument.");
    exit(1);
  }
  //--------------------------------------------------------------
  if (c == 3) {
    count_position= atoi(argv[2]);
    if (count_position == 0) {
        fprintf(stderr, "\nBad command line argument.");
        exit(1);
     }
  } else {
    count_position= strlen(argv[1]);
  }
  //--------------------------------------------------------------
  bytes= strdup(argv[1]);
  if (!bytes) {
        fprintf(stderr,"Not enough memory to allocate buffer for bytes.\n");
        exit(1);
  }
  //--------------------------------------------------------------
  trigger= (char*)malloc(count_position);
  if (!trigger) {
        fprintf(stderr,"Not enough memory to allocate buffer for
trigger.\n");
        free(bytes);
        exit(1);
  }
  for (int cc= 0; cc < count_position; cc++) trigger[cc]= 0;
  //--------------------------------------------------------------
  bytes[0]= '\0';
  pbytes= bytes;
  pargv= argv[1];
  while (*pargv) {
      if (strchr(bytes, *pargv) == 0)
        {
            *pbytes++= *pargv;
            *pbytes= '\0';
        }
    pargv++;
  }
  //--------------------------------------------------------------
  // open a file for output
  sprintf(filename, "%s_%d.txt", argv[1], count_position);
  stream= fopen(filename, "wt+");
  if (!stream)
  {
         fprintf(stderr,"\nError open/create file: %s", filename);
         exit(1);
  }
  fprintf(stream, "\nNumber= %s", argv[1]);
  fprintf(stream, "\nCount position= %d", count_position);
  //--------------------------------------------------------------
  position= count_position - 1;
  count= 1;
  op= PRINT;

  while(1)
  {
     switch(op)
     {
          case PRINT:
          // write some data to the file
          fprintf(stream, "\n");
          fprintf(stream, "%u :", count);

          for (int j = 0; j < count_position; j++)
          {
                   fprintf(stream,"%c", bytes[trigger[j]]);
          }

          if (position != (count_position - 1))
               position= (count_position- 1);

          count++;
          op= NEXT_SYMBOL;
          break;

          case NEXT_SYMBOL:
          trigger[position]++;

          if (trigger[position] == strlen(bytes))
          { // last symbol
                   trigger[position]= 0;
                   op= NEXT_POSITION;
          } else  { // ok
                   op= PRINT;
          }
         break;

          case NEXT_POSITION:
          position--;
          if (position < 0)
          { // exit to DOS
                goto EXIT_TO_DOS;
           } else  { // ok
                op= NEXT_SYMBOL;
          }
          break;
         }// switch
  } // while(1)
  //-----------------------------------------------------------------
EXIT_TO_DOS:
  free(bytes);
  free(trigger);
  // close the file
  fclose(stream);
  //-----------------------------------------------------------------
  fprintf(stdout,
"\n-----------------------------------------------------------------");
  fprintf(stdout, "\nProgramm: %s %s is succefull!", argv[0], argv[1]);
  fprintf(stdout, "\nResult programm save to: [%s]", filename);
  fprintf(stdout, "\nCount= [%d]", count - 1);
  fprintf(stdout,
"\n-----------------------------------------------------------------");
  //-----------------------------------------------------------------
  return 0;
}


Чао!
..... тексты на С и С++ это почти никому ненужный спам.......





--- ifmail v.2.15dev5
 * Origin: UNKNOWN (2:5020/400)