БлогNot. C++: ищем максимальную серию чисел, на которой не выполняется признак

C++: ищем максимальную серию чисел, на которой не выполняется признак

Не так уж редко нам нужно не просто перебрать большое количество последовательно идущих чисел, проверяя их на соответствие некоторому признаку (все цифры числа различны, сумма первых трех цифр равна сумме трех последних, цифры числа упорядочены по возрастанию или убыванию и т.п.), но и выяснить, каков максимальный "зазор" между двумя соседними числами, отвечающими этому признаку (максимальная серия, в которой нет ни одного "счастливого билета", например).

Можно предложить следующий достаточно универсальный алгоритм решения подобных задач:

count=0
Перебрать все числа серии {
 n=очередное_число
 если выполняется_признак {
  массив[count%3]=n
  если (count>0) {
   расстояние = массив[count%3]-массив[(count-1)%3]
   если (расстояние>макс) {
    макс=расстояние
    число1=массив[(count-1)%3]
    число2=массив[count%3]
   }
  }
  иначе {
   число1=0
   число2=макс=массив[0]
  }
  count=count+1
 } 
}
расстояние = массив[(count-1)%3]-массив[(count-2)%3]
если (расстояние>макс) {
 макс=расстояние
 число1=массив[(count-2)%3]
 число2=массив[(count-1)%3]
}
вывести число1, число2, расстояние

Предполагается, что числа перебираются в порядке возрастания, а начало отсчёта - ноль. "Массив" при этом работает как кольцевой буфер размерностью в 3 элемента.

Вот полная реализация на примере поиска максимальной разности между двумя соседними номерами 6-значных "счастливых билетов" (сумма первых трех цифр 6-значного числа равна сумме 3 последних).

#include <stdio.h>

void main () {
 int i,j,k,l,m,n;
 long int count=0,dist=0,max,n1,n2,current[3]={0,0,0};
 for (i=0; i<10; i++)
 for (j=0; j<10; j++)
 for (k=0; k<10; k++)
 for (l=0; l<10; l++)
 for (m=0; m<10; m++)
 for (n=0; n<10; n++)
 if (i+j+k==l+m+n) {
  current[count%3]=(long int)i*100000+(long int)j*10000+k*1000+l*100+m*10+n;
   //не забываем про возможность переполнения при вычислении
  if (count) {
   dist=current[count%3]-current[(count-1)%3];
   if (dist>max) { max=dist; n1=current[(count-1)%3]; n2=current[count%3]; }
  }
  else { n1=0; n2=max=current[0]; } //от 1-го числа до начала отсчета
  count++;
 }
 dist=current[(count-1)%3]-current[(count-2)%3];
  //от последнего числа до предпоследнего
 if (dist>max) { max=dist; n1=current[(count-2)%3]; n2=current[(count-1)%3]; }
 printf ("\nCount=%ld",count);
 printf ("\nNumber1=%06ld, Number2=%06ld, Distance=%ld",n1,n2,max);
 getchar();
}

Если ответ не единственный, найдётся только первый вариант решения. Для поиска последнего из вариантов в сравнениях dist>max нужно заменить знак ">" на ">=". В нашем случае ответов как раз два - пары номеров 000000 и 001001 и 998998 и 999999, в обоих случаях расстояние равно 1001.

Для проверки какого-нибудь другого максимального "расстояния" между числами, отвечающими заданным условиям, могут измениться разве что организация циклов и проверка условия попадания числа в серию. Например, для поиска максимальной разности между 6-значными числами, в которых нет стоящих рядом двух одинаковых цифр, в программе изменится только один оператор:

if (i+j+k==l+m+n) {

на

if (i!=j && j!=k && k!=l && l!=m && m!=n) {

Один из возможных ответов - пара чисел 120101 и 109898.

А вот если различными должны быть все цифры числа, проще написать функцию с переменным числом аргументов, чем громоздить кучу условий:

int all_different(int n, ... ) {
 int *ptr=&n,i,j; ptr++;
 for (i=0; i<n-1; i++)
 for (j=i+1; j<n; j++) {
  if (ptr[i]==ptr[j]) return 0;
 }
 return 1;
}
//...
if (all_different(6,i,j,k,l,m,n)) {

Если нигде не ошибся, ответ здесь единственен:

Count=151200
Number1=000000, Number2=012345, Distance=12345

19.11.2013, 23:15 [10208 просмотров]


теги: c++ алгоритм

К этой статье пока нет комментариев, Ваш будет первым