С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Добавлено через 1 минуту
Если вводим число 18, то программа должна выдать результат "2 3 3"
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2014, 23:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Выведите все простые множители этого числа в порядке неубывания с учетом кратности (рекурсия) (C++):

Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности. - C++
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности. Ввод...

Выведите все простые множители числа в порядке возрастания с учетом кратности - C++
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности. Ввод 18 Вывод 2 3...

Выведите все простые множители числа в порядке возрастания с учетом кратности. - C++
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке возрастания с учетом кратности.

Для целого числа найти и напечатать все простые множители в порядке их возрастания - C++
Для целого числа М найти и напечатать все простые множители в порядке их возрастания. Одинаковые множители печатать столько раз, сколько...

Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае. - C++
пробовала сделать ,но выдаёт ошибки я не понимаю,что он требует ТЕКСТ ЗАДАЧИ. Даны два целых числа A и В (каждое в отдельной...

Рекурсия. Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками - C++
Привет! Начал изучать рекурсию на с++, прочитал несколько статей и понял, что ничего не понял:) Нашел несколько заданий, вот одно из них:...

14
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
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 ...
Помогите закончить программу
0
kiborgdelto
71 / 73 / 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);
}
могу конечно и без считыания (и цикла естественно) попробовать сделать, но тогда сложность программы повысится значительно (нужно будет искать простые числа вручную)
0
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
29.03.2014, 23:05  [ТС] #4
зачем файлы нужны? мне нужно справиться с рекурсией, а не копаться в файлах.
0
kiborgdelto
71 / 73 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:12 #5
в файле лежат простые числа
0
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
29.03.2014, 23:18  [ТС] #6
а если я должен ввести какое-то число, то что должна возвращать функция (см. второй пост темы)

Добавлено через 1 минуту
т.е. должна возвращать простые множители, а как это отобразить в коде? (без циклов и использования файлов, до файлов я еще не дошел)
0
kiborgdelto
71 / 73 / 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);
}
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,493
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;
}
0
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
29.03.2014, 23:33  [ТС] #9
Что такое cin.get(); ? для чего он служит?
0
kiborgdelto
71 / 73 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:38 #10
Цитата Сообщение от Dionisius Посмотреть сообщение
Что такое cin.get(); ? для чего он служит?
cin.get(); считывает введённый символ, в данном случае используется для того чтобы программа выполнила свою работу и дождалась нажатия клавиши enter для выхода из программы
0
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
29.03.2014, 23:40  [ТС] #11
всё, благодарю
0
kiborgdelto
71 / 73 / 27
Регистрация: 23.03.2011
Сообщений: 141
29.03.2014, 23:45 #12
спасибо в карман не положешь
+1 спасибо нажми (в низу поста)
1
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
10.04.2014, 12:55  [ТС] #13
Хочу вернуться к этой программе: хотелось бы, чтобы в коде программы вы добавили функцию, выдававшую на экран не только 2 и 3, но и 5,7,11 и др.простые числа
0
kiborgdelto
71 / 73 / 27
Регистрация: 23.03.2011
Сообщений: 141
10.04.2014, 16:28 #14
если вам нужно чтобы эти числа участвовали в разложении то программа всё правильно выдаёт, к примеру если ввести число 70 то получим числа 2, 5, 7, которые и являются разложением данного числа на простые множители

если же вам нужно вывести таблицу простых чисел то уже несколько другая задача, её можно решить кпримеру через решето эратосфена (код приводился выше)
0
Dionisius
0 / 0 / 0
Регистрация: 19.10.2013
Сообщений: 137
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;
}
Как избавиться от циклов в решете Эратосфена? Рекурсия не требует циклов
0
23.04.2014, 22:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2014, 22:04
Привет! Вот еще темы с ответами:

Выведите все числа от A до B включительно, в порядке возрастания - C++
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A &lt; B,...

Ввести целое число N. Вывести все простые делители этого числа - C++
помогите с двумя задачами... только начали программирование... 1. Ввести целое число N. Вывести все простые делители этого числа ...

Дано целое число n. Получить все простые делители этого числа - C++
Почему простые делители выдает не правильно? ch-число del-делитель dd-делитель делителя #include &quot;stdafx.h&quot; #include...

Ввести целое число N. Вывести все простые делители этого числа - C++
прошу помочь над 2 задачами в с++: 1. Ввести целое число N. Вывести все простые делители этого числа 2. Ввести строку и слово,...


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

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

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