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

  • Переходим на https. Просьба писать обо всех замеченных неисправностях.
  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 3 [Все]   Вниз
  Печать  
Автор Тема: Чисто программисткие задачки  (Прочитано 45820 раз)
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, заметь эта функция анологична моей. И Кнут сделал это на асемблере. Правда я не разбирался до конца как.
Записан

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

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


« Ответ #30 : 07-06-2004 15:08 » 

djyuran,
Цитата
Найти в массиве n-ое число (в порядке сортировки) за O(размера массива)

Я не доконца понял условия. Это найти значение которое стоит на месте n или в отсортированном массиве на n месте. Я склонен предпологать, что ты имел ввиду второй вариант. Я прав?
Записан

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

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

« Ответ #31 : 07-06-2004 15:32 » 

Finch, обмен знаков не поможет, так как знак перекидывать надо только при отрицательном числе.
Записан

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

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

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


« Ответ #32 : 07-06-2004 19:19 » 

npak,
Я думаю, что есть способ. Правда это совсем разврашение.
1. Число загоняеш в регистр
2. Сдвигаеш регистр вправо на 1, побочный эффект бит 7(15) числа перейдет в регистр переполнения. Это знаковый бит.
3. создаеш временную переменную и обнуляеш ее.
4. Делаеш прибавление к этой временной ячейки 0 команндой ADC
5 Достаеш число и меняеш знак у него (NOT числа +1)
6. Еше раз достаеш число
7. Делаеш разницу между числом и его обратным числом
8. Эту разницу умножаеш на временную ячейку.
9. Отнимеш от числа результат умножения.
Записан

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

2Finch: конечно второе Улыбаюсь...
Записан
npak
Команда клуба

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

« Ответ #34 : 08-06-2004 10:37 » 

Finch, похоже на правду Улыбаюсь  Только сдвиг надо делать влево, в сторону старших битов

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

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

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

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


« Ответ #35 : 08-06-2004 14:03 » 

npak,
Это моя ошибка, торопился. Сегодня утром, когда анализировал задачу, понял, что я ошибся.  Да заадно проверил, читает ли кто-нибудь мою галиматью Отлично
Начсет ротации не совсем корректно. Вначале что ты подрузомеваеш под начальным значением флага. Второе покажи на примере:
Число 100 в десятичной системе переводится в двоичную 0110 0100
Число -100 в десятичной системе переводится в двоичную 1001 1100
Число размерностью один байт.
Записан

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

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


« Ответ #36 : 13-06-2004 14:49 » 

djyuran,

Цитата
Найти в массиве n-ое число (в порядке сортировки) за O(размера массива)


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

Код:
1. Создать дополнительный массив записей.
   Каждая запись будет состоять из трех полей
      а: Номер ячейки в сортируемом массиве
      б: Значение ячейки
      в: Ссылка на следующее значение
2. Пройтись по массиву с помошью специальной функции.
Эта функция будет давать вес значения массива.
Согласно этому весу производить запись в массив записей.
Конечно может возникнуть коллизия, когда есть значения с одиноковым весом, для этого сушествует поле )в: в массиве записей
т.е. производить допись в порядке сортировки.
3. Осталось только пройтись по массиву записей и посчитать n-ое значение.
Записан

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

А поиск максимума/минимума и поиск n-ного значения не есть одна и та же задача ? С той разницей, что для хранения значений используется список... Что, в принципе, Finch и предложил.
Записан
Finch
Спокойный
Администратор

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


« Ответ #38 : 16-06-2004 14:48 » 

Skubent,
Сделать поиск максимума и миниума намного проше. Ты заранее знаешь, что меньшего или большого числа в данном массиве нет. А чтобы найти n-ое число из массива, нужно доказать, что в массиве имеется n-1 чисел меньше искомого и N-n (N -  длина массива) чисел больше искомого. Вот тут начинаются приключения. Обычно такая задача решается путем сортировки массива. И после сортировки находится n-ое число. djyuran,  попросил определить только за один проход списка.  Как ты понимаеш, сортировку за один проход очень сложно сделать.
Записан

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

ru
Offline Offline
Сообщений: 13


« Ответ #39 : 28-07-2004 06:11 » 

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

Цитата
npak,
Я думаю, что есть способ. Правда это совсем разврашение.
1. Число загоняеш в регистр
2. Сдвигаеш регистр вправо на 1, побочный эффект бит 7(15) числа перейдет в регистр переполнения. Это знаковый бит.
3. создаеш временную переменную и обнуляеш ее.
4. Делаеш прибавление к этой временной ячейки 0 команндой ADC
5 Достаеш число и меняеш знак у него (NOT числа +1)
6. Еше раз достаеш число
7. Делаеш разницу между числом и его обратным числом
8. Эту разницу умножаеш на временную ячейку.
9. Отнимеш от числа результат умножения.

если это только для того, чтобы отделить знак числа от модуля, то проще так:

если число - 8 битное:
Код:
   mov    al,number8
    cbw
    and    al,01111111b
теперь в al - модуль, во всех битах ah - знак
 
если число - 16 битное:
Код:
   mov    ax,number16
    cwd
    and    ax,0111111111111111b
теперь в ax - модуль, во всех битах dx - знак


если число - 32 битное:
Код:
   mov    eax,number32
    cdq
    and    eax,01111111111111111111111111111111b
теперь в eax - модуль, во всех битах edx - знак


 :arrow:
сортировка массива:
Код:
#define N;
int A[N]
int buf,p=0;

for(i=0;i<N;i++)
{
    if(A[i]<A[p])
    {
        buf=A[p]
        A[p]=A[i];
        A[i]=buf;

        if(p)p--;
        i=p;
    }
    else
    {
        p++;
    }
}
« Последнее редактирование: 25-11-2007 21:16 от Алексей1153++ » Записан

Finch
Спокойный
Администратор

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


« Ответ #40 : 28-07-2004 14:49 » 

Алексей1153,
Цитата
:arrow:
сортировка массива:
Код:
#define N;
int A[N]
int buf,p=0;

for(i=0;i<N;i++)
{
    if(A[i]<A[p])
    {
        buf=A[p]
        A[p]=A[i];
        A[i]=buf;

        if(p)p--;
        i=p;
    }
    else
    {
        p++;
    }
}

А ты ее вообше проверял?
При начальных условиях p=0 и i=0. Поэтому A всегда равна A[p]. И условие пойдет по ветке else. т.е. программа сделает инкримент к p и затем в цикле к i. И так до конца цикла.
И второе: Где гарантия, что программа не будет проверять один и тот же элемент несколько раз. В условии сказано, что можно проверять только один раз.
« Последнее редактирование: 25-11-2007 21:17 от Алексей1153++ » Записан

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

ru
Offline Offline
Сообщений: 13


« Ответ #41 : 28-07-2004 17:57 » 

Finch, ага, не проверял , в спешке писал  Улыбаюсь :?

вместо
for(i=0;i<N;i++)

надо
for(i=1;i<N;i++)

и всё работает - я проверил
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #42 : 28-07-2004 17:58 » 

Цитата

И второе: Где гарантия, что программа не будет проверять один и тот же элемент несколько раз. В условии сказано, что можно проверять только один раз.


будет, каюсь Улыбаюсь
Записан

djyuran
Гость
« Ответ #43 : 02-08-2004 04:45 » 

2Finch: Так и не понял решение про n-ое число. Можешь на программистском языке написать? или подробнее на русском Улыбаюсь!
Записан
Skubent
Гость
« Ответ #44 : 02-08-2004 09:24 » 

Finch, так исходный список мы один раз и будем смотреть. А промежуточный в условии не оговаривался Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #45 : 02-08-2004 10:17 » 

Finch, с учётом встречи в чате :

если число - 8 битное:
Код:


    mov    al,number8
    cbw
    xor    al,ah
    and    ah,1
    add    al,ah

теперь в al - модуль, в младшем бите ah - знак

если число - 16 битное:
Код:

    mov    ax,number16
    cwd
    xor    ax,dx
    and    dx,1
    add    ax,dx

теперь в ax - модуль, в младшем бите dx - знак


если число - 32 битное:
Код:

    mov    eax,number32
    cdq
    xor   eax,edx
    and    edx,1
    add    eax,edx

теперь в eax - модуль, в младшем бите edx - знак
Записан

Finch
Спокойный
Администратор

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


« Ответ #46 : 02-08-2004 14:57 » 

djyuran, а что конкретно ты не понял, просто программистким языком я не вижу смысла писать. Больше мучений, чем толка от такой программы.
Записан

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

Согласно этому весу производить запись в массив записей. - вот эту фразу поподробнее
И "значение ячейки" - это ее вес или первоначальное значение???
Записан
Finch
Спокойный
Администратор

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


« Ответ #48 : 03-08-2004 17:14 » 

djyuran, Ты, как я думаю, заранее знаеш тип данных. Возьмем для примера данные типа Word. Имеет длину два байта. Возьмем старший байт за вес данных. Создаем массив длиной 256. В этом массиве будут хранится ссылки на первую запись данного веса. Теперь вытаскиваем из сортируемого массива число. Определяем его вес и добавляем согласно весу в массив ссылок.
На дельфи определение будет выглядеть примерно так:
Код:
PArr=^TArr;
TArr = record
   Number:word;        /Само число
   Con:integer;          /Порядковый номер в искомом массиве
   Next: PArr;            /ссылка на следуюшую запись того же веса
   End;
ArrArr: array of PArr;
« Последнее редактирование: 25-11-2007 21:19 от Алексей1153++ » Записан

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

Получается, что таким образом ты сортируешь массив...
Скорее всего можно обойтись без этого искусственного приема!
Ответ узнаю только в сентябре - эту задачку нам дали как очень сложную после университетской олимпиады по информатике... так что так просто она не должна решаться!!!

В STL есть такая функция - работает за о(n)
Записан
Finch
Спокойный
Администратор

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


« Ответ #50 : 04-08-2004 19:04 » 

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

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

Вот такую хитрую задачку мне надо будет решить в ближайшие дни:
http://www.djyuran.com/task.txt
Привожу в файле, потому что она и так не понятная, а так разметка потеряется!
Таких я еще не видел. Очень странное условие. Есть у кого-какие предложения. У меня пока только одна идея, да и то какая-то неубедительная Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #52 : 09-08-2004 18:38 » 

вот эта задача
Код:
You are given a file of records, each record has the same unknown length
(or 2-dimensional array of numbers from 0 to 255 where length of row is unknown).
each record consists of fields, each field has length of 1 or more bytes, all fields contain text values.
number and lengths of fields are not known.
write a program that guesses what is the record length in this file.
use statistical analysis techniques that rely on
the empirical fact that fields tend to have similar values.

    example: employee database in a flat file:
    JOHN         SMITH         M    06-11-1964    X
    JANET        JACKSON    F     11-12-1977    Y
    MICHAEL    JACKSON    M    01-12-1967    Z

It is easy for a human to guess what the record length and copmposition of fields is here by looking into
linearized version:
JOHN  SMITH  M  06-11-1964  XJANET  JACKSON  F 11-12-1977 YMICHAEL  JACKSON  M 01-12-1967  Z

Write a program that automates this process.

This program should arrive to a reasonable result in less than
10 minutes for a 1000 record file on standard Windows PC.

у вас есть файл, содержащий записи. Каждая запись имеет одну и ту же длину (но эта длина неизвестна). (Можно представить и так: это двумерный массив чисел от 0 до 255, количество столбцов которого неизвестно.)
Напишите программу, определяющую длину записи в файле.
Используйте технику статистического анализа, основанную на том, что поля записи должны иметь похожие значения (имеется в виду - похожие по формату)

прымер:
Код:
   JOHN         SMITH         M    06-11-1964    X
    JANET        JACKSON    F     11-12-1977    Y
    MICHAEL    JACKSON    M    01-12-1967    Z
человек может легко подсчитать длину и расположение полей, если этот массив написать в одну строку:
Код:
JOHN  SMITH  M  06-11-1964  XJANET  JACKSON  F 11-12-1977 YMICHAEL  JACKSON  M 01-12-1967  Z

напишите программу, автоматизирующую этот процесс.
Программа должна справляться с задачей не более чем за 10 минут для 1000 записей в файле на не самом навороченном компе под управлением OC Windows
« Последнее редактирование: 25-11-2007 21:20 от Алексей1153++ » Записан

djyuran
Гость
« Ответ #53 : 11-08-2004 10:31 » 

Ну вот уже потеряли разметку
должно быть
Код:
JOHN    SMITH     M  06-11-1964  X
JANET   JACKSON   F  11-12-1977  Y
MICHAEL JACKSON   M  01-12-1967  Z

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

Код:
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

vector<int> g_aDivisors; // all divisors of file length

// fill divisor's array of n
void fillDivisorsArray(int n)
{
        int tmp = sqrt(n); // for optimization

        // add to array 1, n and sqrt(n) if n pure square
        g_aDivisors.push_back(1);
        g_aDivisors.push_back(n);
        if (sqrt(n) == tmp)
                g_aDivisors.push_back(tmp);

        // add another divisors
        for (int i = 2; i < tmp; i++)
                if (n % i == 0)
                {
                        g_aDivisors.push_back(i);
                        g_aDivisors.push_back(n / i);
                }
}

// get the similarity score of strings s1 and s2 (len - length of strings)
int getSimilarityScore(char *s1, char *s2, int len)
{
        for (int m = 0, sum = 0; m < len; m++)
        {
                //  abc cb  w
                //  ab  abc e
                //  score = 5
                if (isalpha(s1[m]) && isalpha(s2[m]))
                        sum += 1;

                //  abc 12  2
                //  ab  345 1
                //  score = 6
                if (isdigit(s1[m]) && isdigit(s2[m]))
                        sum += 2;

                // 12-45 a/b m
                // 78-32 e/r m
                // score = 12
                if (s1[m] == s2[m] && !isspace(s1[m]))
                        sum += 4;

                // a b e z e d
                // c d e z r t
                // score = 5
                if (isspace(s1[m]) && isspace(s2[m]))
                        sum += 1;
        }

        return sum;
}

void main(int argc, char *argv[])
{
        // read file in buffer (file name is first parameter of command line)
        if (argc != 2)
        {
                cout << "Invalid parameters\n";
                return;
        }

        FILE *f = fopen(argv[1], "rb");
        if (!f)
        {
                cout << "I/O error\n";
                return;
        }
        fseek(f, 0, SEEK_END);
        long lSize = ftell(f);
        fseek(f, 0, SEEK_SET);
        char* szBuf = new char[lSize + 1];
        fread(szBuf, 1, lSize, f);
        szBuf[lSize] = 0;
        fclose(f);

        // calculate all possible lengthes of record
        fillDivisorsArray(lSize);

        int iMax = 0; // max value score of similarity
        int iLen = -1; // length of record where is max score value

        // calculate appropriate record's length
        for (int i = 0; i < g_aDivisors.size(); i++)
        {
                int k = lSize / g_aDivisors[i]; // concerned record's number

                // compare 1st & 2nd record, 2nd & 3nd, 3nd & 4th etc
                // if we will compare every with every record then this may be slowly
                // records have the same format
                // statisticaly this approach give the same result as full comparing
                char *sTmp = szBuf;
                for (int j = 0, sum = 0; j < k - 1; j++, sTmp += g_aDivisors[i])
                        sum += getSimilarityScore(sTmp, sTmp + g_aDivisors[i], g_aDivisors[i]);

                if (sum > iMax)
                {
                        iMax = sum;
                        iLen = g_aDivisors[i];
                }
        }

        cout << "Solve: " << iLen << endl;
        free(szBuf);
}
« Последнее редактирование: 25-11-2007 21:22 от Алексей1153++ » Записан
djyuran
Гость
« Ответ #54 : 21-09-2004 02:49 » 

Вот оно решение про k-тое число в массиве из n элементов за O(n):

     А. Разобьем наш массив на n/5 групп, в каждой из которых по
5 элементов. Каждую группу упорядочим.
     Б.  Рассмотрим средние элементы всех групп и перепишем их в
массив из n/5 элементов. С помощью  рекурсивного  вызова  найдем
средний по величине элемент этого массива.
     В.  Сравним этот элемент со всеми элементами исходного мас-
сива: они разделятся на большие его и меньшие его (и один равный
ему). Подсчитав количество тех и других, мы узнаем, в  какой  из
этих  частей  должен находится искомый (k-ый) элемент и каков он
там по порядку.
     Г. Применим рекурсивно наш алгоритм к выбранной части.

     Пусть  T(n)  -  максимально  возможное число действий, если
этот способ применять к массивам из не более чем n элементов  (k
может быть каким угодно). Имеем оценку:
     T(n) <= Cn + T(n/5) + T(примерно 0.7n)
Последнее слагаемое объясняется так: при разбиении на части каж-
дая часть содержит не менее 0.3n элементов. В самом деле, если x
-  средний  из средних, то примерно половина всех средних меньше
x. А если в пятерке средний элемент меньше x, то еще два заведо-
мо меньше x. Тем самым по крайней мере 3/5 от половины элементов
меньше x.
    Теперь  по  индукции можно доказать оценку T(n) <= Cn (реша-
ющую роль при этом играет то обстоятельство, что 1/5 + 0.7 < 1).
Записан
Finch
Спокойный
Администратор

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


« Ответ #55 : 02-08-2005 19:44 » 

Недавно встретил задачку. Собственно я знаю решение, просто еше не проверял в коде.
В массиве даны точки описываюшие любую фигуру. Первая точка из массива соединяется линией со второй и т.д. Естественно последняя точка соединяется с первой. Надо посчитать плошадь, которую будет занимать данная фигура.
В принципе задача из жизни имеюшая практическое применение.
Записан

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

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #56 : 03-08-2005 10:28 » 

должны быть еще условия: фигура замкнутая? выпуклая? площадь в пикселях или ед.имерения типа "метр кв."
Записан

Удачного всем кодинга! -=x[PooH]x=-
Alf
Гость
« Ответ #57 : 03-08-2005 11:34 » 

Площадь многоугольника с заданными координатами вершин.

Пусть количество вершин N. Для простоты добавим N+1-ю вершину, совпадающую с первой. Тогда площадь определяется формулой:

A = 1/2 * Si=1N(xi*yi+1 - xi+1*yi)

Источник: Шенен П. и др. Математика и САПР. М.: Мир, 1988. Кн.1, стр. 14, глава 1.3 "Вычисление периметров и площадей".
Записан
Finch
Спокойный
Администратор

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


« Ответ #58 : 03-08-2005 12:38 » 

PooH писал,
Цитата
должны быть еще условия: фигура замкнутая? выпуклая? площадь в пикселях или ед.имерения типа "метр кв."
Pooh, что она замкнута, я хоть и косвенно намекнул. Фигура может быть и выпуклой и вогнутой. Заранее не известно. Задача реальная в картографии. Когда делают замеры координат в крайних точках.

ALf, можно уточнить, эта формула для всех видов фигур. Или только для выпуклых?
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Alf
Гость
« Ответ #59 : 03-08-2005 12:58 » 

Pooh, что она замкнута, я хоть и косвенно намекнул.

Совершенно излишнее упоминание. Незамкнутые фигуры не имеют площади в принципе.

ALf, можно уточнить, эта формула для всех видов фигур. Или только для выпуклых?

Формула универсальная, выпуклость там никак не фигурирует. Кстати, легко выводится, можешь проверить сам.
Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #60 : 03-08-2005 13:08 » 

я ступил, немного, насчет замкнутости - имелось ввиду что линия(периметр) не самопересекающаяся.
Записан

Удачного всем кодинга! -=x[PooH]x=-
npak
Команда клуба

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

« Ответ #61 : 03-08-2005 15:33 » 

ALf, можно уточнить, эта формула для всех видов фигур. Или только для выпуклых?
Цитата

Это формула для многоугольников без самопересечений.
В том случае, когда есть самопересечения, формула даёт неожиданные ответы.
Записан

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

http://www.unitesk.com/ru/
Alf
Гость
« Ответ #62 : 03-08-2005 18:52 » 

На самом деле формула дает положительное значение площади в случае обхода контура против часовой стрелке и отрицательное - по часовой стрелке (100% гарантию не дам, возможно и наоборот). В случае, когда контур самопересекающийся, направление обхода меняется, соответственно и значение получается на первый взгляд странное. В этом случае следует разбить контур на два и более контуров без подобных аномалий и считать площадь каждого из них отдельно. Тем более что с точки зрения топологии площадь самопересекающегося контура - само по себе неожиданное явление.
Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #63 : 04-08-2005 05:24 » 

а как можно площать такой фигуры подсчитать?

ЗЫ. Где можно почитать как вставлять картинки в пост?

* figure.bmp (1.53 Кб - загружено 1036 раз.)
Записан

Удачного всем кодинга! -=x[PooH]x=-
Alf
Гость
« Ответ #64 : 04-08-2005 10:42 » 

"Такой фигуры" - в смысле самопересекающейся?

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

Для данной фигуры:



я бы сначала попросил автора заштриховать область, площадь которой подлежит вычислению. Потому как непонятно, должна ли внутренняя область вычитаться из внешней либо поглощаться ею.
« Последнее редактирование: 04-08-2005 10:48 от Alf » Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #65 : 04-08-2005 10:47 » 

В том-то и дело что у нарисованной мной фигуры однозначно вообще площадь определить нельзя - не понятно: входит внутренняя петля в площадь или нет. И если "Найти точки самопересечения контура и разбить на несколько непересекающихся", то площадь внутренней петли посчитается два раза или не посчитается вообще Жаль

ЗЫ: а как насчет предыдущего "ЗЫ"? Имеется ввиду: не аттачить, а прям в пост вставить.
« Последнее редактирование: 04-08-2005 10:49 от PooH » Записан

Удачного всем кодинга! -=x[PooH]x=-
Alf
Гость
« Ответ #66 : 04-08-2005 10:49 » 

См. исправленный пост выше.
Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #67 : 04-08-2005 10:52 » 

так автора нет! Улыбаюсь Есть условие задачи! В котором  указано: "в массиве даны точки описываюшие любую фигуру." Вот я и запостил, что при отсутствии доп. ограничений задача неразрешима (в общем).
« Последнее редактирование: 04-08-2005 10:53 от PooH » Записан

Удачного всем кодинга! -=x[PooH]x=-
npak
Команда клуба

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

« Ответ #68 : 05-08-2005 09:36 » 

Из опыта общения со специалистами по графическим алгоритмам могу выдвинуть такую формулировку задачи: найти площадь внутри минимального охватывающего контура .
Охватывающий контур -- замкнутая несамопересечённая линия (контур), которая содержит внутри все точки многоугольника.  Минимальный охватывающий контур -- охватывающий контур, который содержится в любом другом охватывающем контуре.  В примере это многоугольник, который получится стиранием внутренней петли.
« Последнее редактирование: 25-11-2007 21:24 от Алексей1153++ » Записан

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

http://www.unitesk.com/ru/
Страниц: 1 2 3 [Все]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines