Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2 3  Все   Вниз
  Печать  
Автор Тема: Чисто программисткие задачки  (Прочитано 45398 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« : 13-05-2004 09:56 » 

Ну, по названию понятно...
Записан

А птичку нашу прошу не обижать!!!
djyuran
Гость
« Ответ #1 : 22-05-2004 14:06 » 

Вот такой Вам вопрос: Что можно сделать в С, но нельзя в С++?
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 23-05-2004 13:45 » 

В С можно так:
 
Код:
f(x, y) { return x+y;}
int g(x, y)
int x, y;
{ return x+y; }

В с++ только так:
Код:
int f(int x, int y) { return x + y; }
int g(int x, int y) { return x + y; }

Более того, в C можно объявить указатель на функцию с нетипизированными аргументами:
Код:
typedef int  (*knr_type)(x, y);

knr_type f1 = f;
knr_type g1 = g;

int d(double x, double y) { return (int)(x+y); }

knr_type d1 = d;
« Последнее редактирование: 25-11-2007 21:05 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 31-05-2004 13:15 » 

Задача -- предложить алгоритм возведения целого положительного числа в куб, пользуясь только сложением.

Число сложений для возведения числа N в куб должно быть O(N).
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
DerSpieler
Гость
« Ответ #4 : 31-05-2004 15:29 » 

Цитата
Число сложений для возведения числа N в куб должно быть O(N).

Что значит "O(N)"?

Можно сначала возвести в квадрат:
S1 = n+n+n+...+n,  n раз.
Потом в куб:
S2 = S1+S1+S1+...+S1, n раз.

Сейчас оптимизирую и тогда можно будет предлагать конкретную реализацию
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 31-05-2004 15:44 » 

DerSpieler, не так сформулировал задачу Жаль

Ты предложил решение за две итерации, каждая с N сложениями.

Можешь за одну итерацию, число операций сложения порядка N?
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 31-05-2004 16:16 » 

Код:
DWORD cub(DWORD N)
   {
     DWORD temp=0;
     DWORD s=0;
     for (DWORD i=N; i>0; i--)
         {
           s=s+N;
           temp=temp+s;
         }
    temp=temp+temp-s;
    return temp;
   }
« Последнее редактирование: 25-11-2007 21:07 от Алексей1153++ » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 31-05-2004 16:48 » 

Finch,  Отлично
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
DerSpieler
Гость
« Ответ #8 : 31-05-2004 18:51 » 

А вот так короче получается
Код:
int cub(int n) {
    int n2=n<<1, Total=n, s=n;
    for (int i=1; i<n; i++)
        Total += s += n2;
    return Total;
}
Проводил тесты производительности, в которых пару сотен миллионов раз прогонял функции. Вот результаты:
1. пустой цикл работает 5с
2. цикл с "S = n*n*n;" работает 7с
3. когда "S = n*n*n;" реализовано в отдельной функции, прога работает 19с
4. моя функция работает 43с
5. функция Finch'a работает 48с
« Последнее редактирование: 25-11-2007 21:09 от Алексей1153++ » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 31-05-2004 20:12 » 

DerSpieler, вот ещё вариант

Код:
unsigned long cube_npak(unsigned long N) {
    unsigned long c = 0, d = 1, e = 6;
    unsigned long i;
    for (i=0; i < N; i++)  {
        c += d;
        d += e;
        e += 6;
    }
    return cube;
}

Вопрос -- почему работает?

Я погонял тесты -- возведение 1000 в куб миллион раз при сильной оптимизации (gcc -O6)
1  решение финча ~3.6 сек
2  твоё решение ~4.5 сек
3  последнее решение ~5.1 сек

Замеры Celeron PIII-750, Windows 2000 Pro, Cygwin
« Последнее редактирование: 25-11-2007 21:10 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
DerSpieler
Гость
« Ответ #10 : 01-06-2004 06:37 » 

Цитата
Вопрос -- почему работает?

Рассмотрим величину R равную
R = n^3 - (n-1)^3 = 3n(n-1)+1.
Т.е. это есть разность между кубами чисел n и n-1. Складывая последовательно числа R(i)=3i(i-1)+1, где i=[1;n], можно получить куб числа n. В твоем решении, npak, это переменная d соответствует R(i).
А теперь о том как обойтись без умножения.
Рассмотрим разность R(i)-R(i-1)=3i(i-1)+1 - (3(i-1)(i-2)+1) = 6(i-1).
Т.е. чтобы найти очередное значение R(i) надо к R(i-1) прибавить 6(i-1), что можно заменить суммой шестерок i-1 раз (переменная е).
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 01-06-2004 09:53 » 

DerSpieler, Точно!
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #12 : 01-06-2004 21:21 » 

Цитата
Я погонял тесты -- возведение 1000 в куб миллион раз при сильной оптимизации (gcc -O6)
1 решение финча ~3.6 сек
2 твоё решение ~4.5 сек
3 последнее решение ~5.1 сек

Замеры Celeron PIII-750, Windows 2000 Pro, Cygwin


npak,  тебе это не кажется странным. Если учесть что у DerSpieler на один раз меньше происходит сложение, чем у меня. С твоим решением понятно почему.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
djyuran
Гость
« Ответ #13 : 04-06-2004 05:03 » 

Задачка: Проверить, есть ли в односвязном списке цикл...
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 04-06-2004 10:52 » 

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

Код:
int has_cycle(list * l) {
list * fast, * slow;
fast = slow = head(l);

fast = next(next(fast));
slow = next(slow);
while(fast != NULL && fast != slow)
{
    fast = next(next(fast));
    slow = next(slow);
}
if (fast == NULL) {
    // цикла нет
    return 0;
} else {
    // цикл есть
    return 1;
}
« Последнее редактирование: 25-11-2007 21:12 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
djyuran
Гость
« Ответ #15 : 04-06-2004 13:45 » 

Знал такое решение, но сразу по нему вопрос, а встретятся ли они? Вдруг быстрый так и будет перескакивать медленный?
Если скажите как код вставлять предложу свое решение Улыбаюсь!?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #16 : 04-06-2004 14:23 » 

djyuran, Быстрый курсор проскакивает два поля. Но сначало происходит скачок на одно поле. Производится проверка по встрече. После этого перескакивается на следуюшее поле. Обратно производится проверка по встрече. После этого медленный курсор скачит на одно поле. Производится проверка по встрече. И так до тех пор пока не встретятся или быстрый не уткнется в NULL.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #17 : 04-06-2004 14:57 » 

djyuran, тебе надо доказательство что они обязательно встретятся?

Пусть в списке длина начала (до цикла) l, длина цикла L

Тогда к тому моменту как медленный курсор войдёт в цикл, расстояние между курсорами будет l.  Условие на встречу -- пройденное расстояние с начала цикла будет отличаться на целое число длин цикла.

пусть s -- расстояние, которое пройдёт до встречи медленный курсор, f -- расстояние, которое пройдёт быстрый курсор.  Тогда
s == f + l (mod L)

Так как быстрый курсор движется в два раза быстрее медленного, то f = 2s

Получаем s == 2s + l (mod L), или s + l == 0 ( mod L )

Если l <= L, то получаем что s == L - l, если l > L, то возьмём l0 = l%L -- остаток от деления l на L и s == L - l0.

Для вставки кода надо обернуть код в пару тегов "code" и "/code" в квадратных скобках

[code]
Your code
[/code]

« Последнее редактирование: 25-11-2007 21:14 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
djyuran
Гость
« Ответ #18 : 04-06-2004 15:09 » 

Вот мое решение:

Код:
template <class T>
struct TElem
{
        T val;
        TElem<T> *pNext;
};

template <class T>
bool hasCycle(TElem<T> *pBegin)
{
        int iter = 0, searchSize = 0;
        TElem<T> *pCycleElem = pBegin;
        for (TElem<T> *pCur = pBegin; pCur->pNext; pCur = pCur->pNext, iter++)
        {
                if (pCur->pNext == pCycleElem)
                        return true;
                if (iter == searchSize)
                {
                        iter = 0;
                        searchSize++;
                        pCycleElem = pCur;
                }
        }
        return false;
}

P.S.: Интересно какое оптимальнее?
Почему нельзя было пустить быстрый в 3 или 4 или n раз быстрее?
« Последнее редактирование: 25-11-2007 21:13 от Алексей1153++ » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #19 : 04-06-2004 15:29 » 

djyuran, в чём назначение searchSize?

Если ты выставишь searchSize равной 2  (не будешь инкрементировать) то получишь улучшенный вариант моего предложения.  Улучшенный в том смысле, что быстрый курсор не будет перескакивать медленный курсор.

При таком подходе можно ставить и 3, и 4, и более скорость быстрого курсора.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
djyuran
Гость
« Ответ #20 : 04-06-2004 16:21 » 

Тут несколько другой принцип - мы каждые searchSize шагов запоминаем начальный элемент и в процессе этих шагов сравниваем с текущим. Если оказались равны, значит есть цикл. Если шаги кончились, то увеличиваем searchSize и продолжаем поиск... У меня движется только один указатель, другой стоит и ждет!

Я тут немного посчитал: вариант с быстрым и медленным указателем выходит быстрее моего, особенно с поправкой от Finch'a!

Интересно другое: вариант с каким n = 2, 3, ... быстрее будет работать?
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #21 : 04-06-2004 16:37 » 

Вот задача, которую я недавно увидел у Кнута, и которая заставила меня задуматся.
В ячейках А и В содержатся соответственно числа а и b. Покажите, что можно написать программу, которая вычисляла  бы min(a,b)  и записывала результат в ячейку С, не пользуясь командами перехода. (Предостережение. Поскольку арефметическое переполнение невозможно обнаружить без операторов перехода, разумно так построить программу, чтобы переполнение не могло возникнуть ни при каких значениях а и b).
"Дональд Кнут. Искусство программирования."
Я пока решил для отыскания минимума. Но на переполнение , есть только предположение.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #22 : 04-06-2004 18:48 » 

djyuran,
Цитата
Интересно другое: вариант с каким n = 2, 3, ... быстрее будет работать?

Если с моей поправкой. То думаю одинаково. Но это будет зависеть от самой цепочки.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
djyuran
Гость
« Ответ #23 : 05-06-2004 01:06 » 

(-abs(a-b) + a+b)/2 = min(a,b) или модулем тоже пользоваться нельзя?
Чтобы без переполнения сейчас подумаю...
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #24 : 05-06-2004 05:30 » 

max(a, b) = a+b-min(a, b), где min(a, b) = (a+b-|a-b|)/2 - см. выше Улыбаюсь

max(a, b) = a+b-(a+b-|a-b|)/2 = a-a/2 + b-b/2 + |a-b|/2 = (a+b+|a-b|)/2
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #25 : 05-06-2004 05:35 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #26 : 05-06-2004 07:07 » 

dimka и djyuran, здесь проблема, что а может быть сверх большой, а b сверх маленькой. Разница между двумя числами очень большая. для примера a-(-b) = ну очень много.
Мое решение без учета переполнения было такое:
C=A-((ABS(A-B)+(A-B))/2)
с переполнением, я думаю так:
C=A-(ABS(A/2-B/2)+(A/2-B/2))
Если A, B, C целочисленные, то нужно вводить еще одну ячейку D
D=(A and 1) - (B and 1) и учитывать ее в последующем.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
djyuran
Гость
« Ответ #27 : 07-06-2004 07:06 » 

Найти в массиве n-ое число (в порядке сортировки) за O(размера массива)
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #28 : 07-06-2004 09:56 » 

Finch, откуда у тебя взялся модуль, если нельзя делать условные переходы?  В твоей машине есть элементарная арифметическая операция взятия модуля?
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #29 : 07-06-2004 14:59 » 

npak, я точно не помню, но в ассемблере есть команды обмена знаков. После своего решения я полез посмотреть, что сделал Кнут. Первое решение такое-же как djyuran, заметь эта функция анологична моей. И Кнут сделал это на асемблере. Правда я не разбирался до конца как.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1] 2 3  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines