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

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

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

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

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

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

Добавлено через 1 минуту
Если вводим число 18, то программа должна выдать результат "2 3 3"
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++
Привет! Начал изучать рекурсию на с++, прочитал несколько статей и понял, что ничего не понял:) Нашел несколько заданий, вот одно из них:...

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

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

если же вам нужно вывести таблицу простых чисел то уже несколько другая задача, её можно решить кпримеру через решето эратосфена (код приводился выше)
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;
}
Как избавиться от циклов в решете Эратосфена? Рекурсия не требует циклов
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. Ввести строку и слово,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.04.2014, 22:04
Ответ Создать тему
Опции темы

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