поиск простых чисел

@turtles1994 · Регистрация: 08.11.2015

Как найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является простым числом.
Формат входных данных:
В единственной строке задано целое положительное число n (n≤20).

Формат выходных данных:
В первой строке вывести ответ

Пример:
input.txt: 3
output.txt: 125

Дали индивидуальное задание по анализу сложности. Только учусь программировать, сам понимаю как можно сделать, но написать код не в состоянии. Однокурсники говорят руку еще не набил.
Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Вроде так

@Renji · 06.12.2016, 07:37

Сообщение от turtles1994

цифр n- значных чисел

Полагаю, слово "цифр" лишнее.

Сообщение от turtles1994

Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Вроде так

И даже это закодить не можете. Вы вообще хоть что-то учили? Ну, в любом случае (особо не тестировал, но вроде бы работает как надо):

C++

    const double table[40]={0.0,
                            9.0,
                            33.0,
                            125.0,
                            477.0,
                            1824.0,
                            6965.0,
                            26646.0,
                            101766.0,
                            389271.0,
                            1487013.0,
                            5687008.0,
                            21728149.0,
                            83085800.0,
                            317484367.0,
                            1213887587.0,
                            4638898052.0,
                            17735216810.0,
                            67780064903.0,
                            259118906269.0,
                            990342206645.0,
                            3785863549035.0,
                            14469910793587.0,
                            55313753020589.0,
                            211419221356513.0,
                            808170398626551.0,
                            3089026962889958.0,
                            11807934066884754.0,
                            45133389029324640.0,
                            172522494320751136.0,
                            659437277165804544.0,
                            2520682382495897600.0,
                            9634929602286983168.0,
                            36829086033511579648.0,
                            140774257691201798144.0,
                            538101314927919824896.0,
                            2056826675492236558336.0,
                            7862078501927142817792.0,
                            30051902340839921156096.0,
                            114871118020094575247360.0};
    int n;
    std::cin>>n;
    std::cout<<table[n];

Нет, где табличку взял - сами думайте.

Байт · 06.12.2016, 13:32

Сообщение от turtles1994

Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику.

Имхо, самый простой, но и самый безобразный в смысле эффективности путь.
Конечно, ни один алгоритм по эффективности не сравнится с предложенным уважаемым Renji,

Но он, увы, требует большой предварительной работы.
Однако, легко заметить, что если стоит цифра 0, то за ней (и перед ней) может стоять только 2, 3, 5, 7
цифра 1 может иметь в соседях только 1, 2, 4, 6
цифра 2 - 0, 1, 3, 5, 9
Такие таблички можно составить для всех 10-цифр.
И подумать немножко...
Не исключен и рекурсивный алгоритм...

@Renji · 06.12.2016, 18:53

Сообщение от Байт

Но он, увы, требует большой предварительной работы.

Строчек сорок, быстренько собранных на коленке и выполняемых за секунду. Единственная сложность тут - задача не на программирование, а на комбинаторику.
Обозначим за F(N,X) число последовательностей из N цифр, в которой каждые две соседние цифры в сумме дают простое число, а первая цифра равна X.
Очевидно, что F(N,X) есть сумма всех F(N-1,Y), для таких Y, которые при сложении с X дают простое число.
Алеоп, у нас есть быстрый рекурсивный вывод F(N,X) из F(N-1,X).
Ну а решение задачи - сумма F(N,1), F(N,2) ... F(N,9). В сумму не включается F(N,0), так как на ноль многозначное число начинаться не может.

Байт · 06.12.2016, 19:39

Сообщение от Renji

задача не на программирование, а на комбинаторику.

Я бы не стал разделять эти два понятия. Скорее, это решение комбинаторной задачи программным способом. Такое случается сплошь и рядом

Сообщение от Renji

Алеоп,

Да, все похоже на правду.

Что-то похожее я имел в виду в конце поста 3
Но я тут придумал неплохой нерекурсивный алгоритм. Пока в лом его писать.... Может быть попозже...Опять же ничего сложного там нет...

Байт · 14.12.2016, 17:42

Сообщение от Байт

Но я тут придумал неплохой нерекурсивный алгоритм. Пока в лом его писать.... Может быть попозже...Опять же ничего сложного там нет...

C++

#include <stdio.h>
#include <stdlib.h>
static int L[10] = { 4, 4, 5, 4, 4, 4, 3, 3, 3, 3 };
static char M[10][5] = {
 { 2,3,5,7,0}, {1,2,4,6,0},
 {0,1,3,5,9 }, {0,2,4,8,0},
 {1,3,7,9,0 }, {0,2,6,8,0},
 {1,5,7,0,0 }, { 0,4,6,0,0},
 {5,5,9,0,0 }, {2,4,8,0, 0 } };
#define N 5
void printX(char *X)
{  int i;
  for(i=0; i<N; i++) printf("%d", X[i]);
  printf("\n");
}
void Full(char *X, int *z, int k)
{ int i;
  for(i=k+1; i<N; i++) {
    X[i] = M[X[i-1]][0];
    z[i] = 1;
  }
}
int main()
{ char *X; int *z, i, count=0;
  X = malloc(N);
  z = malloc(N*sizeof(int));
  X[0] = 1;
  z[0] = 1;
  Full(X, z, 0);
  while(1) {
    // printX(X);   // Печать каждого числа
    count++;
    if (z[N-1] < L[X[N-2]]) X[N-1] = M [X[N-2]] [z[N-1]++];
    else {
      for(i=N-2; i>0; i--) if (z[i] < L[X[i-1]]) break;
      if (i==0) {
        if (X[0] >= 9) break;
        X[0]++;
      }
      else X[i] = M [X[i-1]] [z[i]++];
      Full(X, z, i);
    }
  }
  printf("count=%d\n", count);
  return 0;
}

Случайно получился в Си, но я думаю, это не так важно

@turtles1994 0 / 0 / 0 Регистрация: 08.11.2015 Сообщений: 2
		1
	поиск простых чисел 06.12.2016, 05:41. Показов 1589. Ответов 5 Метки нет (Все метки) Как найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является простым числом. Формат входных данных: В единственной строке задано целое положительное число n (n≤20). Формат выходных данных: В первой строке вывести ответ Пример: input.txt: 3 output.txt: 125 Дали индивидуальное задание по анализу сложности. Только учусь программировать, сам понимаю как можно сделать, но написать код не в состоянии. Однокурсники говорят руку еще не набил. Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Вроде так __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

Байт Диссидент 27191 / 16948 / 3745 Регистрация: 24.12.2010 Сообщений: 38,131
	06.12.2016, 13:32	3
	Сообщение от turtles1994 Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Имхо, самый простой, но и самый безобразный в смысле эффективности путь. Конечно, ни один алгоритм по эффективности не сравнится с предложенным уважаемым Renji, Но он, увы, требует большой предварительной работы. Однако, легко заметить, что если стоит цифра 0, то за ней (и перед ней) может стоять только 2, 3, 5, 7 цифра 1 может иметь в соседях только 1, 2, 4, 6 цифра 2 - 0, 1, 3, 5, 9 Такие таблички можно составить для всех 10-цифр. И подумать немножко... Не исключен и рекурсивный алгоритм... 1

@Renji 2758 / 1912 / 569 Регистрация: 05.06.2014 Сообщений: 5,561
	06.12.2016, 18:53	4
	Сообщение от Байт Но он, увы, требует большой предварительной работы. Строчек сорок, быстренько собранных на коленке и выполняемых за секунду. Единственная сложность тут - задача не на программирование, а на комбинаторику. Обозначим за F(N,X) число последовательностей из N цифр, в которой каждые две соседние цифры в сумме дают простое число, а первая цифра равна X. Очевидно, что F(N,X) есть сумма всех F(N-1,Y), для таких Y, которые при сложении с X дают простое число. Алеоп, у нас есть быстрый рекурсивный вывод F(N,X) из F(N-1,X). Ну а решение задачи - сумма F(N,1), F(N,2) ... F(N,9). В сумму не включается F(N,0), так как на ноль многозначное число начинаться не может. 1

Байт Диссидент 27191 / 16948 / 3745 Регистрация: 24.12.2010 Сообщений: 38,131
	06.12.2016, 19:39	5
	Сообщение от Renji задача не на программирование, а на комбинаторику. Я бы не стал разделять эти два понятия. Скорее, это решение комбинаторной задачи программным способом. Такое случается сплошь и рядом Сообщение от Renji Алеоп, Да, все похоже на правду. Что-то похожее я имел в виду в конце поста 3 Но я тут придумал неплохой нерекурсивный алгоритм. Пока в лом его писать.... Может быть попозже...Опять же ничего сложного там нет... 1

Опции темы

поиск простых чисел

Решение