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

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

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

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

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

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

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

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

Вход

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

Выход

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


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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
07.03.2014, 16:24     Найти наименьшее общее кратное (НОК) n натуральных чисел #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;
}
Dani
1278 / 636 / 56
Регистрация: 11.08.2011
Сообщений: 2,277
Записей в блоге: 2
Завершенные тесты: 1
12.03.2014, 00:16  [ТС]     Найти наименьшее общее кратное (НОК) n натуральных чисел #3
VaniaKosmos, а ты сдать ее попробуй туда. Я подумал - тут длинка нужна и всё.
VaniaKosmos
0 / 0 / 0
Регистрация: 07.03.2014
Сообщений: 3
12.03.2014, 10:09     Найти наименьшее общее кратное (НОК) n натуральных чисел #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;
}
Yandex
Объявления
12.03.2014, 10:09     Найти наименьшее общее кратное (НОК) n натуральных чисел
Ответ Создать тему
Опции темы

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