Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
turtles1994
0 / 0 / 0
Регистрация: 08.11.2015
Сообщений: 2
#1

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

06.12.2016, 05:41. Просмотров 260. Ответов 5
Метки нет (Все метки)

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

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

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

Дали индивидуальное задание по анализу сложности. Только учусь программировать, сам понимаю как можно сделать, но написать код не в состоянии. Однокурсники говорят руку еще не набил.
Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Вроде так
http://www.cyberforum.ru/cpp-beginners/thread2233749.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2016, 05:41
Я подобрал для вас темы с готовыми решениями и ответами на вопрос поиск простых чисел (C++):

Поиск простых чисел
Почему мне возвращает просто непарные числа? в чем загвоздка #include...

Поиск простых чисел
Знаю, что тема избитая, но решил написать алгоритм поиска простых чисел. int...

Поиск простых чисел
Народ, в программе нужно из введённых чисел найти и вывести простые числа(т.е....

Поиск простых чисел
#include <iostream> #include <stdio.h> #include <locale.h> using namespace...

Поиск простых чисел
3. Разработать программу поиска простых чисел в отрезке (1..N) целых...

5
Renji
2127 / 1486 / 453
Регистрация: 05.06.2014
Сообщений: 4,326
06.12.2016, 07:37 #2
Лучший ответ Сообщение было отмечено turtles1994 как решение

Решение

Цитата Сообщение от turtles1994 Посмотреть сообщение
цифр n- значных чисел
Полагаю, слово "цифр" лишнее.
Цитата Сообщение от turtles1994 Посмотреть сообщение
Так вот, думаю... Можно сделать функцию, где есть цикл до 999. И в каждый раз когда она генерирует новую комбинацию проверить просуммировать соседние, разбив на a b c. Если условие удовлетворяет +1 к счетчику. Вроде так
И даже это закодить не можете. Вы вообще хоть что-то учили? Ну, в любом случае (особо не тестировал, но вроде бы работает как надо):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    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];
Нет, где табличку взял - сами думайте.
2
Байт
Эксперт C
17765 / 11790 / 2449
Регистрация: 24.12.2010
Сообщений: 23,711
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
2127 / 1486 / 453
Регистрация: 05.06.2014
Сообщений: 4,326
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
Байт
Эксперт C
17765 / 11790 / 2449
Регистрация: 24.12.2010
Сообщений: 23,711
06.12.2016, 19:39 #5
Цитата Сообщение от Renji Посмотреть сообщение
задача не на программирование, а на комбинаторику.
Я бы не стал разделять эти два понятия. Скорее, это решение комбинаторной задачи программным способом. Такое случается сплошь и рядом
Цитата Сообщение от Renji Посмотреть сообщение
Алеоп,
Да, все похоже на правду.
Что-то похожее я имел в виду в конце поста 3
Но я тут придумал неплохой нерекурсивный алгоритм. Пока в лом его писать.... Может быть попозже...Опять же ничего сложного там нет...
1
Байт
Эксперт C
17765 / 11790 / 2449
Регистрация: 24.12.2010
Сообщений: 23,711
14.12.2016, 17:42 #6
Цитата Сообщение от Байт Посмотреть сообщение
Но я тут придумал неплохой нерекурсивный алгоритм. Пока в лом его писать.... Может быть попозже...Опять же ничего сложного там нет...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}
Случайно получился в Си, но я думаю, это не так важно
2
14.12.2016, 17:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2016, 17:42
Привет! Вот еще темы с решениями:

Поиск простых чисел
помогите пожалуйста с заданием напишите программу которая при помощи двух...

Поиск простых чисел
необходимо найти все простые числа от 1 до 100. Вот я написал код: #include...

Поиск простых чисел
to idetify if the given K is prime or not. Prime number is the number that can...

Поиск простых чисел на диагоналях
В двумерном массиве A, состоящем из n × n целых чисел, вычислить: • наименьший...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru