Форум программистов, компьютерный форум CyberForum.ru

Вывести последовательность элементов, сумма которых будет простым числом. - C++

Восстановить пароль Регистрация
 
micr0
0 / 0 / 0
Регистрация: 10.04.2010
Сообщений: 9
08.12.2011, 11:45     Вывести последовательность элементов, сумма которых будет простым числом. #1
Дан одномерный массив.Выввести последовательность элементов, сумма которых будет простым числом.
Размерность небольшая - к примеру 7. Числа целые до 10.
Проблема в том, что прога выводи только по 3 числа в последовательности а нужно выводить все.
Например сегодня тестил программу:
Размерность массива 7, заполнил такими элементами - 1,2,2,3,2,4,1
В итоге вывело несколько последовательностей эл-тов в сумме дающих 5,7.
А должно было вывести: 1+1=2 1+2=3 1+2+2=5 1+2+2+3+2+1=11 1+2+2+3+4+1=13 2+2+3=7 2+3+2=7 2+3+2+1=11.
Помогите пожалуйста сделать так, чтобы выводило все последовательности элементов.
Вот листинг:

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
47
48
49
50
51
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
 
void main()
{
    clrscr();
 
    // zadaem massiv iz 15 slychainih chisel
    int M[100], d, n;
    cout<<"\n Vvedite razmernost n =";
    cin>>n;
    for (d = 1; d <= n; d++)
    {
 
        cout <<"M["<<d<<"]=";
        cin >> M[d];
        cout<<"\n";
    }
    cout << endl;
 
    for (int i = 0; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            for (int k = j + 1; k <= n; k++)
            {
                int sum = M[i] + M[j] + M[k];
                //opredelyaem prostaya li summa
 
                if (sum == 0 || sum == 1)
                    cout << M[i] << " + " << M[j] << " + " << M[k] << " = " << sum << " - prostoe" << endl;
                else
                {
                    for (int q = 2; q < sum; q++)
                    {
                        if (sum % q == 0)
                            goto m;
 
                    }
                    cout << M[i] << " + " << M[j] << " + " << M[k] << " = " << sum << " - prostoe" << endl;
                    m:
                }
 
            }
        }
    }
 
 
    getch();
}
 Комментарий модератора 
Используйте теги форматирования кода!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 11:45     Вывести последовательность элементов, сумма которых будет простым числом.
Посмотрите здесь:

C++ Вывести наибольшее из целых чисел К,для которых сумма 1+2+...+К будет меньше или равна N, и саму эту сумму.
Вывести наибольшее из целых N, для которых сумма 1+1\2+...+1\N будет меньше А, и саму эту сумму. C++
C++ Назовем число красивым, если сумма квадратов его цифр является простым числом
Цикл: Определить все числа, принадлежат промежутку [10,99], сумма цифр которых является простым числом. C++
C++ Определить и вывести на консоль пары значений, сумма которых будет парным числом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13951 / 8782 / 1221
Регистрация: 24.12.2010
Сообщений: 15,891
08.12.2011, 12:03     Вывести последовательность элементов, сумма которых будет простым числом. #2
C
1
2
3
4
5
6
7
8
9
10
11
int sk; // Используется как битовая шкала:i-тый бит= 1 - M[i] входит в сумму
int Max = (1<<n); 
for(sk=1; sk<Max; sk++) {
  for(i=sum=0; i<n; i++)
    if (sk&(1<<i)) sum+=M[i];
  if (Prostoe(sum)) {
   for(i=sum=0; i<n; i++)
     if (sk&(1<<i)) cout<<"+" <<M[i];
   cout<< "="<<sum<<endl;
  }
}
Функцию Prostoe , надеюсь, сделаешь сам. Твой алгоритм определения простоты числа не самый эффективный, но вполне рабочий.
Удачи!
ЗЫ. Оформляй код тегами! А то попадет...
Kidasov
76 / 76 / 12
Регистрация: 02.12.2011
Сообщений: 966
Записей в блоге: 3
08.12.2011, 12:11     Вывести последовательность элементов, сумма которых будет простым числом. #3
Функция проверки на простоту

C++
1
2
3
4
5
6
7
8
9
10
bool isDigit(int number)
{
  bool flag = false;
  if (!number) { flag = true; return flag; }
  for (int i=2; i<=number/2; i++)
  {
    if (number % i == 0) {flag = true; break;}
  }
  return flag;
}
Байт
 Аватар для Байт
13951 / 8782 / 1221
Регистрация: 24.12.2010
Сообщений: 15,891
08.12.2011, 12:18     Вывести последовательность элементов, сумма которых будет простым числом. #4
C
1
2
3
4
5
6
7
8
9
bool isProstoe(int number)
{  int M;
  if (number<=1) return false;
  if (number==2) return true;
  M = sqrt(n);
  for (int i=3; i<M; i+=2)
    if (number % i == 0) return true; 
  return false;
}
micr0
0 / 0 / 0
Регистрация: 10.04.2010
Сообщений: 9
08.12.2011, 12:19  [ТС]     Вывести последовательность элементов, сумма которых будет простым числом. #5
Спасибо большое! Теперь нада только вместе это всё собрать как то))
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
08.12.2011, 22:36     Вывести последовательность элементов, сумма которых будет простым числом. #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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
 
#define N  8
 
int buf[1000];
int bufp;
int sum;
 
void process_term(int pos, int *arr, int size);
 
int main()
{
    /* 
     * There is a one trick: the sequence is preceded by zero,
     * fake-element, which are the other terms processed by. 
     */
    int arr[N] = {0, 1, 2, 2, 3, 2, 4, 1};
    int i, b;
    
    printf("Sequence:");
    for (i = 1; i < N; i++)
        printf(" %d", arr[i]);
    putchar('\n');
 
    process_term(0, arr, N);
    
    for (i = 0; i < bufp; i++) {
        for (b = 1; b < N; b++) {
            if (buf[i] & (1 << b)) 
                printf("%d ", arr[b]);
        }
        printf("\n");
    }
    return 0;
}
 
int isprime(int);
 
void process_term(int pos, int *arr, int size)
{
    int localbuf, localsum;
 
    buf[bufp] |= 1 << pos;
    sum += arr[pos];
 
    localbuf = buf[bufp];
    localsum = sum;
 
    if (isprime(sum) && sum != arr[pos]) {
        bufp++;
        buf[bufp] = buf[bufp - 1];
    }
    for (pos += 1; pos < size; pos++) {
        process_term(pos, arr, size);
        sum = localsum;
        buf[bufp] = localbuf;
    }   
}
 
int isprime(int n)
{
    int i;
 
    for (i = 2; i < n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}
вывод
Sequence: 1 2 2 3 2 4 1
1 2
1 2 2
1 2 2 3 2 1
1 2 2 3 4 1
1 2 2 2
1 2 2 2 4
1 2 3 2 4 1
1 2 3 4 1
1 2 3 1
1 2 2
1 2 4
1 2
1 2 3 2 4 1
1 2 3 4 1
1 2 3 1
1 2 2
1 2 4
1 3 2 4 1
1 3 2 1
1 3 1
1 2
1 2 4
1 4
1 1
2 2 3
2 2 3 2 4
2 2 3 4
2 2 2 4 1
2 2 2 1
2 2 1
2 3
2 3 2
2 3 2 4
2 2 1
2 4 1
2 1
2 3
2 3 2
2 3 2 4
2 2 1
2 4 1
2 1
3 2
3 4
2 4 1
2 1
4 1
Press any key to continue . . .


Есть "повторы", но они из разных элементов т.е.
1 2(второй элемент)
1 2(третий элемент)
при желании, можно убрать и их.
Сосредаточился на основной задаче, поэтому проверку на простату сделал самую тривиальную.
Да и размер буфера можно вычислить и память выделять динамически.

Байт, не смог понять ваш алгоритм : (
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2011, 11:15     Вывести последовательность элементов, сумма которых будет простым числом.
Еще ссылки по теме:

C++ В двоичном дереве удалить все узлы, значения которых является простым числом
Определить, является ли сумма цифр этого числа простым числом C++
C++ Определить количество пар чисел сумма которых является простым числом

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

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13951 / 8782 / 1221
Регистрация: 24.12.2010
Сообщений: 15,891
09.12.2011, 11:15     Вывести последовательность элементов, сумма которых будет простым числом. #7
Цитата Сообщение от Net_Wanderer Посмотреть сообщение
Байт, не смог понять ваш алгоритм : (

Не по теме:

А ты подвинься на край ущелья и вниз бросайся...


Попробуй оттранслировать и запустить. Не будет работать - горе мне!

Добавлено через 11 часов 43 минуты
Несколько описочек в определении простоты числа (на что мне указали компетентные товарищи)
Вот исправленный код
C
1
2
3
4
5
6
7
8
9
bool isProstoe(int number)
{  int M;
  if (number<=1) return false;
  if (number==2) return true;
  M = sqrt(number);
  for (int i=3; i<=M; i+=2)
    if (number % i == 0) return false; 
  return true;
}
Приношу свои извинения
Yandex
Объявления
09.12.2011, 11:15     Вывести последовательность элементов, сумма которых будет простым числом.
Ответ Создать тему
Опции темы

Текущее время: 04:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru