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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
#1

Найти наименьшее общее кратное (НОК) n натуральных чисел - C++

15.12.2011, 23:33. Просмотров 2195. Ответов 3
Метки нет (Все метки)

Есть задача:
условие
НОК

Найти наименьшее общее кратное (НОК) n натуральных чисел.

Технические условия

Вход

В первой строке задано количество чисел n (1 < n < 21). Во второй строке находится n натуральных чисел, не превышающих 100 и разделенных пробелом.

Выход

НОК заданных чисел.


Тут нормальное условие
Написал обычный алгоритм типа НОК = (a*b)/Nod(a,b); Но получается превышение лимита времени на последнем тесте. Как с этим бороться?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2011, 23:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти наименьшее общее кратное (НОК) n натуральных чисел (C++):

Найти наименьшее общее кратное (НОК) натуральных чисел С++ - C++
Вот мой исходник : #include &lt;iostream.h&gt; int NSD (int a, int b) { while (a!=0 &amp;&amp; b!=0) { if (a&gt;b) { ...

Найти НОК (наименьшее общее кратное) массива натуральных чисел - C++
Найти НОК (наименьшее общее кратное) массива натуральных чисел. Спасибо за помощь :)

Найти наименьшее общее кратное (НОК) n натуральных чисел (оптимизировать код) - C++
Здравствуйте! Вот еще одна несложная задачка, однако 10/11 (последний тест не прошел по времени). НОК пытался вычислять разными методами,...

Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B - C++
Задача 7. Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B.

Найти НОК (наименьшее общее кратное) двух введённых чисел - C++
Найти НОК (наименьшее общее кратное) двух введённых чисел. Спасибо за помощь

Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел. - C++
Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел.

3
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
07.03.2014, 16:24 #2
Предельно простая задача даже для начинающего как я. Нужно лишь чуток подумать)
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
int nsd (int a, int b){ //НОД
    
    if (b == 0) {
        return a;
    }
    
    return nsd(b, a%b);
}
 
int main(){
 
    int n, b, c = 1;
    
    cin >> n; //водим количество наших чисел
    
    for(int i = 0; i < n; i++){
        
        cin >> b; //вводим каждое число отдельно
        
        c = c*b / nsd(c, b); //класическое нахождее НОД от двух переменных
    }
    cout << c << endl;  //вот и результат
    return 0;
}
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.03.2014, 00:16  [ТС] #3
VaniaKosmos, а ты сдать ее попробуй туда. Я подумал - тут длинка нужна и всё.
0
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
12.03.2014, 10:09 #4
Странно. В подобной задаче с таким использованием НОК все прошло. Даже с лонг лонгом 1 тест не проходит. Буть может тут специфический случай. Потому что явную ошибку я не вижу(
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
#include "stdio.h"
#include "math.h"
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
LL nsd (LL a, LL b) {
    if (b == 0)
        return a;
    return nsd(b, a%b);
}
 
int main(){
    
    int n, b;
    LL c = 1;
    
    cin >> n; //водим количество наших чисел
    
    for(int i = 0; i < n; i++){
        
        cin >> b; //вводим каждое число отдельно
        
        c = c*b / nsd(c, b); //класическое нахождее НОД от двух переменных
    }
    cout << c << endl;  //вот и результат
    return 0;
}
0
12.03.2014, 10:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2014, 10:09
Привет! Вот еще темы с ответами:

Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел - C++
Напишите пожалуйста код =)

Написать программу, вычисляющую НОК (наименьшее общее кратное) двух целых чисел - C++
2. Написать программу, вычисляющую НОК (наименьшее общее кратное) двух целых чисел. Поиск НОК вынести в отдельную функцию.

Определить наименьшее общее кратное двух натуральных чисел - C++
вот мой код. выдаёт одну ошибку. помогите пожалуйста найти. #include&lt;iostream.h&gt; main(int nok) { int a, b, nod, nok; ...

Вычислить наименьшее общее кратное двух натуральных чисел - C++
Написать программу, вычисляющую наименьшее общее кратное двух натуральных чисел a) Найти max (a, b). Числа a, b должны вводится с...


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

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

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