Задание для бабуши! Выполнить на руби.

Lord_Evil · 24-06-11 15:36:47

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?

Все остальные желающие могут присойденится и быдлокодить на своих любимых языках.

SemyonKozakov · 24-06-11 15:46:40

Lord_Evil, зачем на руби-то? yikes Это же чисто математическая задача. Ответ (как я быстренько посчитал): 12 252 240

Добавлено спустя 07 мин 55 с:
Быдлорешение на быдлопетончеге:

i = 0

while True:
    i += 1
    isdel = True
    for j in range(1,21):
        if i % j != 0:
            isdel = False
    if isdel == True:
        print(i)
        break

(Очень) банальный перебор. До сих пор дожидаюсь его результатов. Нормальное решение, возможно, запостю позже.

ikkunan salvataja · 24-06-11 16:01:35

SemyonKozakov пишет:

Ответ (как я быстренько посчитал): 12 252 240

Видимо у меня калькулятор неправильный, выдаёт что 12252240/19 это приблизительно 644854,7368421052631578947368421052631578947368421052631578947368

SemyonKozakov · 24-06-11 16:05:21

ikkunan salvataja, миль пардон. Торопился посчитать smile В любом случае это чистая математика без программирования.

Гареев Станислав · 24-06-11 16:10:00

Lord_Evil пишет:

Все остальные желающие могут присойденится и быдлокодить на своих любимых языках.

Метод перебора. это же очевидно.

SemyonKozakov · 24-06-11 16:12:27

В приницпе, если рассматривать программирование и общий случай (самое маленькое число, которое делится на все числа от 1 до n), то путь решения виден такой:

Создать пустой массив для делителей числа
Поочерёдно разложить все числа от 1 до n на множители
После каждого разложения добавлять недостающие и только недостающие множители в список
Перемножить делители в итоге

Добавлено спустя 01 мин 30 с:

Гареев Станислав пишет:

Метод перебора. это же очевидно.

Флаг в руки перебирать. Я уже выложил скрипт для перебора. На моём двухядерном процессоре он до сих пор ответ ищет.

ikkunan salvataja · 24-06-11 16:25:42

SemyonKozakov пишет:

Создать пустой массив для делителей числа
Поочерёдно разложить все числа от 1 до n на множители
После каждого разложения добавлять недостающие и только недостающие множители в список
Перемножить делители в итоге big_smile

Найти все простые меньшие заданного N методом Sieve of Eratosthenes. При получении первого простого, да и последующих тоже, берём не само простое, а его степень не превышающую N и поочерёдно производим домножение.
UPD: Несколько сумбурно выразился, не показатель степени не должен превышать N, а простое в этой степени, т.е. применительно к данному случаю
2^4⋅3^2⋅5⋅7⋅11⋅13⋅17⋅19

Отредактировано ikkunan salvataja (24-06-11 16:32:01)

SemyonKozakov · 24-06-11 16:30:09

Кстати, полностью правильный ответ задачи: 232792560

ikkunan salvataja пишет:

Найти все простые меньшие заданного N методом Sieve of Eratosthenes.

Можно нескромный вопрос? Это так решето Эрастофена из школьный программы на английском звучит? Я не понимаю, зачем его писать именно на английском.

ikkunan salvataja · 24-06-11 16:35:34

SemyonKozakov пишет:

Я не понимаю, зачем его писать именно на английском.

Ну во всяких учебниках по програманию оно именно так пишется. Привычка.

Майор Очевидность · 24-06-11 17:18:00

слишком уж простое задание, ящетаю.
дайте-ка что-нибудь из олимпиадного программирования подкину.
euler.jakumo.org/problems/view/340.html — вот, например.

Lord_Evil · 24-06-11 18:33:35

ikkunan salvataja пишет:

Найти все простые меньшие заданного N методом Sieve of Eratosthenes. При получении первого простого, да и последующих тоже, берём не само простое, а его степень не превышающую N и поочерёдно производим домножение.

Эт понятно. Ждем реализации от бабуши smile Хочу увидеть идею в коде воплощенной.

Майор Очевидность пишет:

дайте-ка что-нибудь из олимпиадного программирования подкину.

Злой ты, этого и я так просто не осилю..

Babusha · 24-06-11 19:55:37

Я сейчас далек от своего ноута, комп не мой, но решение на Си, методом перебора, через часик будет на руби:

# include <stdio.h>

int main()
{
    int a = 1;
    while(1)
    {
            a++;
            printf("%d\n",a);
            int c = 0;
            int b; 
            for(b = 1; b <= 20; b++)
            {
                    if((a % b) != 0) c = 1;
            }
            if(c == 0)
            {
                 printf("%d",a);
                 int ch = getchar();
                 break;
            }
    }
}

SemyonKozakov · 24-06-11 19:57:44

Babusha, судя по коду, через часик ты только цифру дождёшься. Посмотри на ответ (232 792 560) и подумай, сколько раз компьютер будет проверять все числа от 1 до ответа на деление нацело.

Babusha · 24-06-11 20:06:08

SemyonKozakov, у меня решение на си посчитало за ~30 сек. Это твой говногалимый петун будет считать три часа, вместе с руби, который в данном плане не лучше себя поведет.

usr_share · 24-06-11 20:15:04

Мдя. Туповатенькое решение. У меня оно за 30 секунд дошло только до одного миллиона.

Гареев Станислав · 24-06-11 20:19:18

SemyonKozakov пишет:

сколько раз компьютер будет проверять все числа от 1 до ответа на деление нацело.

Интересно, а на асме примеры будут?

Майор Очевидность · 24-06-11 20:22:18

Гареев Станислав,
после того, как алгоритм решения выложили, лично мне писать уже неинтересно, хотя и сам алгоритм со, скажем так, «обратной факторизацией», был очевиден.

Lord_Evil · 24-06-11 21:11:06

Babusha, я забыл уточнить - смысл решения этих задач в том, чтобы само решение состояло из минимального числа итераций. Икуна очень хорошо выше объяснил, как оформить решение. Иначе если у тебя будет напр. в задании число 100, то можешь представить, сколько оно будет считать. У Семена вообще походу камп сгорит big_smile

ikkunan salvataja · 24-06-11 21:26:29

Lord_Evil пишет:

смысл решения этих задач в том, чтобы само решение состояло из минимального числа итераций.

Я бы ещё порекомендовал вначале выставить флаг показателя степени, т.е. как только мы выяснили что квадрат очередного простого больше N, мы этот флаг сбрасываем и дальнейшие проверки, а не будет ли N больше квадрата, куба итд этого простого, проводить не будем. В случае ассемблера можно вообще подмахнуть код, т.е. в начало процедуры этой проверки подставить код джампа на процедуру домножения.
Правда в винде или линуксе за это мы сразу получим segmentation fault, но в DOS или OS/2 это покатит и даст ощутимый выигрыш в быстродействии.

Lord_Evil · 24-06-11 22:20:43

Вот еще задача интересная:
euler.jakumo.org/problems/view/4.html

Число-палиндром с обеих сторон (справа и слева) читается одинаково. Самое большое число-палиндром, полученное произведением двух двухзначных чисел – 9009 = 91х99.

Найдите самый большой палиндром, полученный произведением двух трёхзначных чисел.

Tiphon · 24-06-11 23:00:04

Слегка оптимизированный перебор. Вспоминать руби времени не было)) 0.16 сек на нетбуке.

Вообще, мне кажется (но ужо точно не помню) был у этой задачи другой вариант решения, но он, в отличии от перебора, требует размышлений)

using System;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static int Brute(int[] numbers )
        {
            int delta = numbers[numbers.Length - 1];
            for (int value = delta; ; value += delta)
            {
                bool result = true;
                foreach (var number in numbers)
                {
                    if (value % number != 0)
                    {
                        result = false;
                        break;
                    }
                }
                if(result) return value;
            }
        }

        static void Main(string[] args)
        {
            var numbers = Enumerable.Range(1, 20).ToList();
            
            //start timer
            Stopwatch timer = new Stopwatch();
            timer.Start();

            //array filtration
            for(int right = 0; right<numbers.Count; right++)
            {
                int rightIndex = numbers.Count - 1 - right;

                for (int left = 0; left < rightIndex; left++)
                {
                    if (numbers[rightIndex] % numbers[left] == 0)
                    {
                        numbers.RemoveAt(left);
                        left--;
                        rightIndex--;
                    }
                }
            }

            int value = Brute(numbers.ToArray());
            
            //stop timer
            timer.Stop();

            //see what we've got after filtration and result
            numbers.ForEach(Console.WriteLine);
            Console.WriteLine("End in {0} ms. Value is {1}", timer.ElapsedMilliseconds, value);
        }
    }
}

Майор Очевидность · 24-06-11 23:02:13

Tiphon, ну так обратная факторизация же.
находим наименьшее общее кратное чисел с 1 по 20 — и вуаля.

Tiphon · 24-06-11 23:12:22

Майор Очевидность пишет:

Tiphon, ну так обратная факторизация же.
находим наименьшее общее кратное чисел с 1 по 20 — и вуаля.

И?

Мы разве где-то спорим?

Майор Очевидность · 24-06-11 23:16:52

Tiphon,
ну, просто, не понял зачем перебор, когда НОК требует примерно столько же мыслительной активности smile
впрочем, сужу по себе, поэтому наверняка необъективен.

Дестер · 24-06-11 23:39:42

Lord_Evil пишет:

Вот еще задача интересная:
euler.jakumo.org/problems/view/4.html

Ничего интересного, решается в две строчки.
Кажется, так:

▼Скрытый текст

Отредактировано Дестер (24-06-11 23:50:26)

Форум StopLinux

Объявление

#1 24-06-11 15:36:47

Задание для бабуши! Выполнить на руби.

#2 24-06-11 15:46:40

Re: Задание для бабуши! Выполнить на руби.

#3 24-06-11 16:01:35

Re: Задание для бабуши! Выполнить на руби.

#4 24-06-11 16:05:21

Re: Задание для бабуши! Выполнить на руби.

#5 24-06-11 16:10:00

Re: Задание для бабуши! Выполнить на руби.

#6 24-06-11 16:12:27

Re: Задание для бабуши! Выполнить на руби.

#7 24-06-11 16:25:42

Re: Задание для бабуши! Выполнить на руби.

#8 24-06-11 16:30:09

Re: Задание для бабуши! Выполнить на руби.

#9 24-06-11 16:35:34

Re: Задание для бабуши! Выполнить на руби.

#10 24-06-11 17:18:00

Re: Задание для бабуши! Выполнить на руби.

#11 24-06-11 18:33:35

Re: Задание для бабуши! Выполнить на руби.

#12 24-06-11 19:55:37

Re: Задание для бабуши! Выполнить на руби.

#13 24-06-11 19:57:44

Re: Задание для бабуши! Выполнить на руби.

#14 24-06-11 20:06:08

Re: Задание для бабуши! Выполнить на руби.

#15 24-06-11 20:15:04

Re: Задание для бабуши! Выполнить на руби.

#16 24-06-11 20:19:18

Re: Задание для бабуши! Выполнить на руби.

#17 24-06-11 20:22:18

Re: Задание для бабуши! Выполнить на руби.

#18 24-06-11 21:11:06

Re: Задание для бабуши! Выполнить на руби.

#19 24-06-11 21:26:29

Re: Задание для бабуши! Выполнить на руби.

#20 24-06-11 22:20:43

Re: Задание для бабуши! Выполнить на руби.

#21 24-06-11 23:00:04

Re: Задание для бабуши! Выполнить на руби.

#22 24-06-11 23:02:13

Re: Задание для бабуши! Выполнить на руби.

#23 24-06-11 23:12:22

Re: Задание для бабуши! Выполнить на руби.

#24 24-06-11 23:16:52

Re: Задание для бабуши! Выполнить на руби.

#25 24-06-11 23:39:42

Re: Задание для бабуши! Выполнить на руби.

Подвал форума