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

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

Формула универсальная, выпуклость там никак не фигурирует. Кстати, легко выводится, можешь проверить сам.
Записан
Страниц: 1 [2] 3  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines