crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )


  Ответ в найти самое круглое число между двумя заданными
Введите ваше имя
Подтвердите код

Введите в поле код из 6 символов, отображенных в виде изображения. Если вы не можете прочитать код с изображения, нажмите на изображение для генерации нового кода.
 

Опции сообщения
 Включить смайлы?
Иконки сообщения
(Опционально)
                                
                                
  [ Без иконки ]
 


Последние 10 сообщений [ в обратном порядке ]
Iron Bug Дата 20.3.2010, 20:57
  но только ты удостоверься, что компилер правильно понимает твою конструкцию:
int c = i2/d*d;
а то он может и соптимизировать :) так что лучше сначала подели и приведи к целому, а потом умножай.
mezmay Дата 20.3.2010, 20:46
 
int round(int i1, int i2)// 0<= i1 < i2
{
    int result;

    int cel[3];
    cel[0] = 1;
    cel[1] = 2;
    cel[2] = 5;

    bool in = true;

    while(in)
    {
        int i=0;
        while(i<3)
        {
            int d = cel[i];
            int c = i2/d*d; // главная мысль!
            if(c < i1)         //
            {
                if(i == 0)
                    result = cel[0]/2;
                else
                    result = cel[i-1];
                in = false;
                break;
            }
            i++;
        }
        for(int j=0; j<3; j++)
            cel[j]*=10;
    }
    return i2/result*result;
}

есть!!!
Iron Bug Дата 20.3.2010, 20:33
  ну, во первых, расмотрим, к примеру, делитель 5. если число не делится на 5, то он не делится на 50, 500 и т.д. следовательно, можно сначала просто проверять делимость на 5. очевидно, что каждое пятое число натурального ряда делится на 5.
так что можно для начала делить, скажем, на 5 и смещаться по единице. в пределах первых пяти чисел будет найдено число, которое будет делиться на пять. далее, найдя это число, которое делится на 5, его можно проверить на делимость на 50, 500 и т.д, и после него уже можно идти не со смещением +1, а со смещением +5. так как между ними уже гарантированно ничего на 5 не делится. аналогично и с двойкой и прочими числами. так что это можно сразу отсекать и даже не проверять. уже экономия операций.
на основе делимости можно изобрести более хитрый алгоритм. скажем, обнаружив, что мы можем идти со смещением не +5, а +50 или +500 - сначала двигаться с таким смещением, пока не выйдем за пределы интервала.
аналогично, в несколько проходов, проверять остальные числа ряда А, порождённые основаниями 1 и 2.
mezmay Дата 20.3.2010, 20:20
 
Цитата(BRE @ 20.3.2010, 17:23) *
Если работать с целыми числами, то я бы начал пробовать с этого:
int round( int I1, int I2 )
{
        return ((I1 + I2) / 2) / 10 * 10;
}


на основе этой идеи придумал новый алгоритм. спасибо!!!
15 мин :)
mezmay Дата 20.3.2010, 19:14
 
Цитата(BRE @ 20.3.2010, 18:56) *
Все равно я не очень понял.
А напиши ряд круглых чисел:
10, 20, 50, ...
или как он должен выглядеть?

(121, 199) = 150
А (121, 202) = ? Чему должен быть равен?


... 10, 20, 50, ... - это не все круглые числа, а как бы основа всех круглых...))

Короче передо мной стояла задача найти самое круглое число между двумя заданными.
Первый вопрос который у меня возник - "а что такое круглое число ваще??"
Я попытался формализовать это понятие так:
Определение. "Даны два целых числа а и в. Дан числовой ряд А: 1, 2, 5, 10, 20, 50, 100, 200, 500, ....
САМЫМ КРУГЛЫМ ЧИСЛОМ МЕЖДУ ДВУМЯ ЗАДАННЫМИ называется такое число с, которое делится на член ряда А с максимальным номером.
Ряд А формируется умножением массива 1,2,5 на 10 на 100 на 1000 и так далее"

f(121, 202) будет число 200, так как оно делится аж на 200
BRE Дата 20.3.2010, 18:56
  Все равно я не очень понял.
А напиши ряд круглых чисел:
10, 20, 50, ...
или как он должен выглядеть?

(121, 199) = 150
А (121, 202) = ? Чему должен быть равен?
mezmay Дата 20.3.2010, 18:27
 
Цитата(BRE @ 20.3.2010, 17:23) *
f(121, 199) = 150;
А в этом случае ответ точно должен быть 150, а не 160?

Что должна вернуть функция, при:
f(22, 23) = ?

Если работать с целыми числами, то я бы начал пробовать с этого:
int round( int I1, int I2 )
{
        return ((I1 + I2) / 2) / 10 * 10;
}


Опиши подробней свойства функции.


В идеале функция должна возвращать те же значения, которые выдает моя.
Опищу свойства этого самого требуемого круглого числа:

на примере (121, 199):

как в исходнике написано, основа всех круглых чисел - числа 1,2,5, потом они умножаются
на 10 и получается тройка 10, 20, 50, ... 1000, 2000, 50000, ...
Итак, нам на вход поступили числа 121 и 199. Рассматриваем все числа в заданном диапазоне.
Делим каждое из них на 1, на 2 , на 5, потом умножаем массив на 10 и делим каждое уже на 10, 20, на 50.
на 100 ни одно из чисел заданного диапазона не делится, следовательно, самое большое число, на которое
разделилось одно из чисел диапазона - 50. Ему соответствует значение 150. его и возвращаем!

Функция f(22, 23) должна вернуть 22
BRE Дата 20.3.2010, 17:23
  f(121, 199) = 150;
А в этом случае ответ точно должен быть 150, а не 160?

Что должна вернуть функция, при:
f(22, 23) = ?

Если работать с целыми числами, то я бы начал пробовать с этого:
int round( int I1, int I2 )
{
        return ((I1 + I2) / 2) / 10 * 10;
}


Опиши подробней свойства функции.
maint Дата 20.3.2010, 17:22
 
Цитата(mezmay @ 20.3.2010, 16:35) *
а не проще с конца для скорости искать ? Если самое большое нужно ?

mezmay Дата 20.3.2010, 16:35
  Нужна функция, которая бы быстро могла найти самое круглое целое число между двумя заданными. Например:
f(9, 11) = 10;
f(121, 199) = 150;
f(1, 9999) = 5000;

есть моя медленная реализация (долго на больших, сильно удаленных друг от друга числах):
int round(const int &I1, const int &I2)
{
    register int i1 = I1;
    register int i2 = I2;
    int result = -1;

    //основа всех круглых чисел
    register int cel[3];
    cel[0] = 1;
    cel[1] = 2;
    cel[2] = 5;

    int znak = 1;
    if(i2<0)
    {
        int sw = i1;
        i1 = -i2;
        i2 = -sw;
        znak = -1;
    }
            // ноль - самое круглое число
    if(i1 < 0 && i2 > 0 || i1 == 0 || i2 == 0 )
        result = 0;
    else
    {    
                        // в общем случае делим каждое из чисел, расположенных
                        //между заданными, на круглые из массива (пока делятся)
        register int count = 0;
        register int j=0;
        do
        {
            register int i = i1;
            register int cnt = 0;
            do
            {
                if(i%cel[j] == 0)
                {
                    cnt ++;
                    result = i;
                }
                i++;
                count  = cnt;
            } while (cnt < 1 && i < i2);
            j++;
            if(j == 3)
            {
                for(int k=0; k<3; k++)
                    cel[k] *= 10;
                j=0;
            }
        } while (count > 0);
    }
    return result*znak;    
}


вопрос - КАК сделать это быстрее?
Просмотр темы полностью (откроется в новом окне)
RSS Текстовая версия Сейчас: 28.3.2024, 18:34