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

Майор Очевидность · 26-06-11 15:25:42

Дестер,
это я ему когда-то предлагал исследовать умножение в столбик по первому и последнему разрядам результата, и тем самым получить задачу перебора 10×10 по второму разряду.
насколько он меня тогда понял, судить сложно, т.к. код совершенно нечитаем.

Lord_Evil · 26-06-11 17:56:08

Дестер, да, ты прав, что-то я или не дописал, как хотел или перемудрил.. давно дело было)

TrollWINNT · 28-06-11 21:25:20

Lord_Evil пишет:

Вот решишь предложенную Майором задачу euler.jakumo.org/problems/view/340.html и тогда мы дружно признаем, что ты крутой авторитет

Что то компилер с ума спрыгивает smile . Тупой вопрос, 7^21 это скока? Просто у двух компиляторов си мнения капитально расходятся с виндовым калькулятором, а на глаз прав именно калькулятор big_smile . Разница в младших разрядах, а как раз младшие то разряды хоть как нужны smile .

ikkunan salvataja · 28-06-11 21:42:02

TrollWINNT пишет:

Тупой вопрос, 7^21 это скока?

558545864083284007

MOP3E · 28-06-11 21:45:38

Lord_Evil пишет:

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

Мдя. Моя твоя не понимай. Программа выполняется меньше, чем за секунду. Число итераций там равно квадрату заданного числа, то есть для 20 это будет 400. Не так уж и много и уж точно не "в лоб", так как внутренний цикл в большинстве случаев выполняется "в холостую". А у тебя, по моим прикидкам, получается 1000 итераций. Кстати, как ты решал проблему переполнения при 32-разрядных вычислениях?

Lord_Evil пишет:

Ухты ёлки.. мб я на своем острове отстал от жизни, но всегда считал, подписывание имен переменных иначе, чем на английском, дурным тоном.

Можешь подписывать свои переменные исключительно на английском. Лично я знаю оба языка и использую тот, который мне в данный момент удобнее.

Отредактировано MOP3E (28-06-11 21:52:13)

TrollWINNT · 28-06-11 22:20:15

ikkunan salvataja пишет:

558545864083284007

И виндовый кальк так же говорит. А Си почему то уверен что 558545864083284030, несмотря на long double smile
В результате у моего быдлокода нет шансов smile

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <math.h>


long double A,B,C,D;
long double F_n(long double n)
{
long double f=0;
                  //D=3*(A-C);
                 while (n<=B)
                        {
                        n=n+A;
                        f=f+D;
                        }
                 f=f+(n-C);
return f;
}

int main(void)
{
 long double f,n=0,n1=0,s=0,s1=0;//A,B,C;
  // A=pow(21,7);
  // B=pow(7,21);
  // C=pow(12,7);

   A=50;
   B=2000;
   C=40;
   D=3*(A-C);
    
    //f=F_n(n); 

    // while (n<=B)
    //  {
    //    s=s+F_n(n);
    //     n++;
    //  }
      while (n1<B)
        {
        n1=n1+A;
        s1=s1+A*((F_n(n1)-A)+((A+1)/2));
        }s1=s1+F_n(0);

   //printf(" \n %Lf %Lf %Lf",A,B,C);
   //printf(" \n %Lf %Lf %Lf",f,s,s1);
      printf(" \n %Lf",s1);
   getch();
   return 0;
}

Хотя у него и так нет шансов, явно нужен другой подход smile

MOP3E · 28-06-11 22:23:27

Открою страшную тайну. Эта задачка решается банальным подбором числа в MS Excel!

ikkunan salvataja · 28-06-11 22:32:55

TrollWINNT пишет:

А Си почему то уверен что 558545864083284030, несмотря на long double

Майкрософтовский? Ну этот может, у них помнится на каком то калькуляторе значение синуса могло достигать восьми, даже в мирное время.

MOP3E · 28-06-11 22:36:03

ikkunan salvataja пишет:

Майкрософтовский?

Я бы на твоём месте не позорился, а взял в руки бумагу и ручку и посчитал результат.

ikkunan salvataja · 28-06-11 22:44:33

MOP3E пишет:

Я бы на твоём месте не позорился, а взял в руки бумагу и ручку и посчитал результат.

Да пожалуйста, хоть 7^221, на
5843416508321765137412223462176261055753559544095817424625430781485355014524409616639950700057743469282269362223748969437289370453147445512994056218802090543396973006957507863824356124007

mav · 28-06-11 22:46:39

ikkunan salvataja пишет:

Майкрософтовский? Ну этот может,

Этому верите?
www.wolframalpha.com/input/?i=7^21

TrollWINNT · 28-06-11 22:47:01

ikkunan salvataja пишет:

Майкрософтовский? Ну этот может, у них помнится на каком то калькуляторе значение синуса могло достигать восьми, даже в мирное время.

Калькуль то как раз выдает нормально. Просто для таких чисел встроеных в С типов данных маловато будет smile . У long double 15 знаков точности. Ну и учитывая что при степени B = 17 считается 30 секунд для 21 это около 3 дней smile . Явно не то решение.

MOP3E · 28-06-11 22:49:59

Итак, объясняю основную математическую идею:
1. Число в любом случае должно состоять из произведения всех простых числе последовательности [1;20]:
1*2*3*5*7*11*13*17*19 = 9699690.

2. Полученное число нужно проверить делением на все не простые числа последовательности [1;20]:
2.1. Остаток от деления 9699690 на 4 будет 2 - следовательно, число нужно домножить: 9699690 * 4/2 = 19399380;
2.2. Остаток от деления 19399380 на 8 будет 4 - следовательно, число нужно домножить: 19399380 * 8/2 = 38798760;
2.3. Остаток от деления 38798760 на 9 будет 3 - следовательно, число нужно домножить: 38798760 * 9/3 = 116396280;
2.4. Остаток от деления 116396280 на 16 будет 8 - следовательно, число нужно домножить: 116396280 * 16/8 = 232792560.

3. Так как число 232792560 делится без остатка на все числа последовательности [1;20] - это и есть результат вычислений.

Кстати, получили результат за 20 итераций. Меньше вряд ли получится.

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

TrollWINNT пишет:

Калькуль то как раз выдает нормально. Просто для таких чисел встроеных в С типов данных маловато будет

Нужно ковырять 64-битную целочисленную арифметику, тогда - получится. Спецбиблиотеки юзать или самому что-то сочинять.

Отредактировано MOP3E (28-06-11 22:51:29)

ikkunan salvataja · 28-06-11 22:56:51

mav пишет:

Этому верите?

Верю, оно с моим совпадает.
А 7^221 я на всякий случай проверил. Во
zalil.ru/31351408

TrollWINNT · 28-06-11 22:58:45

MOP3E пишет:

Нужно ковырять 64-битную целочисленную арифметику, тогда - получится. Спецбиблиотеки юзать или самому что-то сочинять.

Это не решение. Время вычисления получится несколько дней, а нужно только несколько младших разрядов. Должна быть какая то бяка позволяющая это сделать проще smile

ikkunan salvataja · 28-06-11 23:00:01

MOP3E пишет:

Кстати, получили результат за 20 итераций. Меньше вряд ли получится.

Ты #7 случаем не пропустил?

MOP3E · 28-06-11 23:03:17

ikkunan salvataja пишет:

Ты #7 случаем не пропустил?

Пропустил.

ikkunan salvataja · 28-06-11 23:06:46

MOP3E пишет:

Пропустил.

Маладэц, а теперь посчитай сколько итераций там. Можешь воспользоваться калькулятором.

MOP3E · 28-06-11 23:06:52

TrollWINNT пишет:

Это не решение. Время вычисления получится несколько дней, а нужно только несколько младших разрядов.

Блин. Погляди мой код хотя бы - где там несколько дней? Там 400 итераций на всё вычисление, причём можно уменьшить до 210. Даже если представлять 64-битное число не нативно, а, чтобы избежать переполнения, четырьмя 16-битными числами, всё равно получится меньше секунды реального времени.

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

ikkunan salvataja пишет:

Маладэц, а теперь посчитай сколько итераций там.

20 итераций чтобы перемножить простые числа и ещё 20 - чтобы выполнить проверку делением. Меньше сделать невозможно.

Ну, как вариант - 20 итераций чтобы выделить степени простых чисел, которые складываются в промежуточный массив, а потом ещё 9 итераций на умножение. Но тогда потребуется ещё один массив.

Отредактировано MOP3E (28-06-11 23:10:25)

TrollWINNT · 28-06-11 23:13:41

MOP3E пишет:

Блин. Погляди мой код хотя бы - где там несколько дней? Там 400 итераций на всё вычисление, причём можно уменьшить до 210.

Мы говорим о различных задачах. Я вобще то об этой euler.jakumo.org/problems/view/340.html

ikkunan salvataja · 28-06-11 23:21:32

MOP3E пишет:

Ну, как вариант - 20 итераций чтобы выделить степени простых чисел, которые складываются в промежуточный массив, а потом ещё 9 итераций на умножение. Но тогда потребуется ещё один массив.

Не, видно не совсем внимательно читал.
Итак,
a=1
ищем первое простое равное 2.
ищем максимальную степень этого простого не превышающую 20, т.е 4
a=a*2^4
ищем второе простое, т.е 3.
ищем максимальную степень 3 не превышающую 20, нашли.
a=a*3^2
следующее простое - 5, 5^2>20 поэтому устанавливаем флаг отключающий возведение простого в степень и сравнение с 20
a=a*5
a=a*7
Итд.

MOP3E · 28-06-11 23:22:03

TrollWINNT пишет:

Я вобще то об этой

Не понял второй записи:
F(n) = F(a + F(a + F(a + F(a + n))))
Как это будет вычисляться?

TrollWINNT · 28-06-11 23:40:41

MOP3E пишет:

Не понял второй записи:
F(n) = F(a + F(a + F(a + F(a + n))))
Как это будет вычисляться?

Для данных из примера a = 50, b = 2000 и c = 40
для n=2000
2000 = 2000 то есть 2 формула
F(a+n) => F(50+2000) 2050>2000 то есть F(2050) = n-c = 2050-40 =2010 =>
F(a+F(n)) => F(50 + 2010) = 2020
F(a+F(n)) => F(50 + 2020) = 2030
F(a+F(n)) => F(50 + 2040) = 2040
Как то так. Несколько сумбурно, но я нихрена не математик smile . С F(0) все еще тоскливее. 0+50 < 2000 => то есть возвращаемся на функцию и добавляем еще 50 . И так пока выражение в скобках не достигнет 2000. А потом все по цепочке назад. Куча вложений выходит. У меня значение функции для данных из задания и n=0 около 2 секунд считает smile .

Добавлено спустя 56 мин 19 с:
Если бы B делилось на A - можно бы было прикинуть младшие разряды по такой формулке
s=F_n(B)+(B/A)*((3*(A-C))+(A/2));
А так... придется наверное выделять остаток и считать smile

Babusha · 13-07-11 17:01:10

Раскопаем труп тему, но это надо запостить!

Haskell:

main = do print $ foldl lcm 1 [1..20]

$ time ./hello.exe
232792560

real    0m0.069s
user    0m0.031s
sys     0m0.015s

fooser · 02-06-12 13:21:53

usr_share пишет:

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

Такое решение тратит много времени на пропечатку вариантов. Лучше уж так:

/*
    compile with:
    ____________________

    gcc -std=c99 -O3 -Wall -Werror ./file.c
*/

#include <stdio.h>
#include <stdbool.h>

int main( void )
{

    int a = 0;
    int b = 1;
    int c = 20;
    bool d = false;
    int e = 0;

    while(1)
    {
        a++;
        e++;

        if( e == 10000000 )
        {
            printf( "Passed %d...\n", a );
            e = 0;
        }

        for( b = 1; b <= c; b++ )
        {
            if((a % b) != 0)
            {
                break;
            }
            else
            {
                if( b == c )
                {
                    printf("Result: %d\n",a);
                    d = true;
                }
            }
        }

        if( d == true )
        {
            break;
        }
    }

    return(0);
}

Тогда строка "Passed %d ..." будет выдаваться каждые 10 миллионов вариантов, что снизит нагрузку за счет вывода лишней инфы.

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

Babusha пишет:

Раскопаем труп тему, но это надо запостить!
Haskell:
main = do print $ foldl lcm 1 [1..20]
$ time ./hello.exe
232792560

real    0m0.069s
user    0m0.031s
sys     0m0.015s

А вы уверены что в эксешнике вообще есть алгоритм? Код мог быть соптимизирован компилятором и содержать только результат.

Отредактировано fooser (02-06-12 13:25:43)

Форум StopLinux

Объявление

#51 26-06-11 15:25:42

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

#52 26-06-11 17:56:08

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

#53 28-06-11 21:25:20

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

#54 28-06-11 21:42:02

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

#55 28-06-11 21:45:38

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

#56 28-06-11 22:20:15

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

#57 28-06-11 22:23:27

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

#58 28-06-11 22:32:55

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

#59 28-06-11 22:36:03

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

#60 28-06-11 22:44:33

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

#61 28-06-11 22:46:39

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

#62 28-06-11 22:47:01

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

#63 28-06-11 22:49:59

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

#64 28-06-11 22:56:51

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

#65 28-06-11 22:58:45

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

#66 28-06-11 23:00:01

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

#67 28-06-11 23:03:17

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

#68 28-06-11 23:06:46

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

#69 28-06-11 23:06:52

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

#70 28-06-11 23:13:41

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

#71 28-06-11 23:21:32

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

#72 28-06-11 23:22:03

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

#73 28-06-11 23:40:41

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

#74 13-07-11 17:01:10

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

#75 02-06-12 13:21:53

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

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