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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 110
22.03.2014, 23:55     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) #1
Дано натуральное число 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 до n (Рекурсия) C++
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности. C++
Выведите все простые множители числа в порядке возрастания с учетом кратности. C++
C++ Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.
C++ Выведите все простые множители числа в порядке возрастания с учетом кратности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 110
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
Сообщений: 110
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
Сообщений: 110
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
Модератор
 Аватар для Catstail
21436 / 10221 / 1666
Регистрация: 12.02.2012
Сообщений: 17,097
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
Сообщений: 110
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
Сообщений: 110
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
Сообщений: 110
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     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия)
Еще ссылки по теме:

C++ Выведите все числа от A до B включительно, в порядке возрастания
РЕКУРСИЯ-----дано натуральное число N. выведите все цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками. При решении этой за C++
Рекурсия. Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками C++

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

Или воспользуйтесь поиском по форуму:
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 110
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     Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия)
Ответ Создать тему
Опции темы

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