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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
#1

Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) - C++

22.03.2014, 23:55. Просмотров 1619. Ответов 14
Метки нет (Все метки)

Дано натуральное число n>1. Выведите все простые множители этого числа в порядке неубывания с учетом кратности.Алгоритм должен иметь сможность O(logn).
Это задача на рекурсию, без использования циклов. Без рекурсии задачу у меня не примут.

Добавлено через 1 минуту
Если вводим число 18, то программа должна выдать результат "2 3 3"
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2014, 23:55     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия)
Посмотрите здесь:
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности. C++
Выведите все простые множители числа в порядке возрастания с учетом кратности. C++
C++ Выведите все простые множители числа в порядке возрастания с учетом кратности
C++ Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.
Рекурсия. Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками C++
РЕКУРСИЯ-----дано натуральное число N. выведите все цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками. При решении этой за C++
C++ Выведите все числа от A до B включительно, в порядке возрастания
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
29.03.2014, 22:14  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #2
Что мне удалось создать, но я не закончил:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <conio.h>
int main()
{
    int n;
    int prostch;
    scanf("%d", &n);
    prostch=prost(n);
    printf ("%d", prostch);
}
int prost (int n)
{
    if ...
Помогите закончить программу
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:03     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #3
могу предложить только такой вариант, цикл используется только при считывании простых чисел в массив, для последующего поиска разложения на простые числа
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
#include <iostream>
#include <iomanip> 
#include<locale>
#include <fstream>
using namespace std;
 
int prost_chisl(int* chisl, int n);
int prost_del(int *chisl,int n1, int k1);
 
void main (void) 
 {
    setlocale(LC_ALL,"Rus");
    int n,k; 
   cout<<"Введите число\n";
   cin>>n;
   int *chisl= new int [n];
   k=prost_chisl(chisl, n);
   cout<<"Разложение на простые множители:\n";
   prost_del(chisl,n,0);
    cin.get();
    cin.get();
    delete [] chisl;
 }
 
int prost_chisl(int* chisl, int n)
   {
       
       ifstream fp ("C:\\числа.txt");
       if ( ! fp ) 
       {
            cout << "ошибка: не могу открыть входной файл " << endl;
            system("pause");
            exit(0);
        }
 
       int i=0,k=0;
       do
       {
       fp >>chisl[i];
       i++;
       }
        while(n>chisl[i-1]);
        k=i-1;
       fp.close();
       return k;
   }
 
int prost_del(int *chisl,int n1, int k1)
{
    if(n1%chisl[k1]==0||n1==1)
    {
        cout<<chisl[k1]<<endl;
        n1=n1/chisl[k1];
        k1=0;
        if(n1==1) return 0;
        prost_del(chisl,n1, k1);
    }
    else prost_del(chisl,n1, k1+1);
}
могу конечно и без считыания (и цикла естественно) попробовать сделать, но тогда сложность программы повысится значительно (нужно будет искать простые числа вручную)
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
29.03.2014, 23:05  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #4
зачем файлы нужны? мне нужно справиться с рекурсией, а не копаться в файлах.
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:12     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #5
в файле лежат простые числа
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
29.03.2014, 23:18  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #6
а если я должен ввести какое-то число, то что должна возвращать функция (см. второй пост темы)

Добавлено через 1 минуту
т.е. должна возвращать простые множители, а как это отобразить в коде? (без циклов и использования файлов, до файлов я еще не дошел)
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:24     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #7
в приведённой выше программе всё это есть, функция prost_del


вот рабочая программа, без циклов и файлов с рекурсией
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
#include <iostream>
#include<locale>
#include <fstream>
#include <cmath>
using namespace std;
 
int prost_del(int n1, int n);
int prost_c(int n, int k);
 
void main (void) 
 {
   setlocale(LC_ALL,"Rus");
   int n; 
   cout<<"Введите число\n";
   cin>>n;
   cout<<"Разложение на простые множители:\n";
   prost_del(n,2);
   cin.get();
   cin.get();
}
 
int prost_del(int n1,  int n)// функция проводит разложение числа n1 на простые множители, n 1-t простое число (2)
{
    int t;
    t=prost_c(n, 2);
    if(n1%t==0||n1==1)
    {
        cout<<t<<endl;
        n1=n1/t;
        if(n1==1) return 0;
        prost_del(n1,  2);
    }
    else prost_del(n1, t+1);
}
 
int prost_c(int n, int k)// вычисляет следующее за n простое число (кроме n=2)
{
    if(n==2||n%k!=0&&k>=sqrt((double)n)) return n;
    else    if(k<sqrt((double)n)) prost_c(n,k+1);
            else prost_c(n+1,2);
}
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,978
29.03.2014, 23:31     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #8
Цитата Сообщение от Dionisius Посмотреть сообщение
Помогите закончить программу
- точнее, начать и кончить...

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
#include <iostream.h>
 
// Решето Эратосфена
 
void Sieve(int *P, int k)
{
    int i,j;
    for (i=1; i<=k; i++) P[i]=i;
    for (j=2; j<=k; j++)
        if (P[j] != 0) for (i=2; i*j<=k; i++) P[i*j]=0;
}
 
// Разбиение на простые множители
 
void Factor(int n, int k, int *P)
{
    if (n == 1)
        return;
    else
        if ((P[k]==0) || ((n%k) != 0))
            Factor(n,k+1,P);
        else
            {
                cout << k << " ";
                Factor(n/k,k,P);
            }
}
 
// Главная
 
int main(int argc, char* argv[])
{
    int n, *E;
    cout << "n=";
    cin >> n;
    E=new int[n/2+1];
    Sieve(E,n/2);
    Factor(n,2,E);
    cout << endl;
    delete [] E;
    return 0;
}
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
29.03.2014, 23:33  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #9
Что такое cin.get(); ? для чего он служит?
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:38     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #10
Цитата Сообщение от Dionisius Посмотреть сообщение
Что такое cin.get(); ? для чего он служит?
cin.get(); считывает введённый символ, в данном случае используется для того чтобы программа выполнила свою работу и дождалась нажатия клавиши enter для выхода из программы
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
29.03.2014, 23:40  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #11
всё, благодарю
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:45     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #12
спасибо в карман не положешь
+1 спасибо нажми (в низу поста)
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
10.04.2014, 12:55  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #13
Хочу вернуться к этой программе: хотелось бы, чтобы в коде программы вы добавили функцию, выдававшую на экран не только 2 и 3, но и 5,7,11 и др.простые числа
kiborgdelto
70 / 72 / 27
Регистрация: 23.03.2011
Сообщений: 141
10.04.2014, 16:28     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #14
если вам нужно чтобы эти числа участвовали в разложении то программа всё правильно выдаёт, к примеру если ввести число 70 то получим числа 2, 5, 7, которые и являются разложением данного числа на простые множители

если же вам нужно вывести таблицу простых чисел то уже несколько другая задача, её можно решить кпримеру через решето эратосфена (код приводился выше)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2014, 22:04     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия)
Еще ссылки по теме:
Ввести целое число N. Вывести все простые делители этого числа C++
Ввести целое число N. Вывести все простые делители этого числа C++
C++ Дано целое число n. Получить все простые делители этого числа
C++ Разложить число на простые множители и записать их в обратном порядке
Найти все простые числа от 1000 до 1999, в каждом из которых сумма первой и второй цифр в записи этого числа равна сумме третьей и четвертой. C++

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

Или воспользуйтесь поиском по форуму:
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 136
23.04.2014, 22:04  [ТС]     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #15
Имеется эта программа:
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
#include <stdio.h>
#include <conio.h>
// ГђГҐГёГҐГІГ® ГќГ°Г*òîñôåГ*Г*
 
void Sieve(int *P, int k)
{
    int i,j;
    for (i=1; i<=k; i++) P[i]=i;
    for (j=2; j<=k; j++)
        if (P[j] != 0) for (i=2; i*j<=k; i++) P[i*j]=0;
}
 
// ГђГ*çáèåГ*ГЁГҐ Г*Г* ïðîñòûå Г¬Г*îæèòåëè
 
void Factor(int n, int k, int *P)
{
    if (n == 1)
        return;
    else
        if ((P[k]==0) || ((n%k) != 0))
            Factor(n,k+1,P);
        else
            {
                printf("%d", k);
                Factor(n/k,k,P);
            }
}
 
 // ГѓГ«Г*ГўГ*Г*Гї
 
int main(int argc, char* argv[])
{
    int n, *E;
    printf("n=");
    scanf("%d", &n);
    E=new int[n/2+1];
    printf("Razlozhenie na prostye mnozhiteli :\n");
    Sieve(E,n/2);
    Factor(n,2,E);
    getch ();
    return 0;
}
Как избавиться от циклов в решете Эратосфена? Рекурсия не требует циклов
Yandex
Объявления
23.04.2014, 22:04     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия)
Ответ Создать тему
Опции темы

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