Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сравнение

Автор: rash 3.10.2006, 22:00

Требуется сравнить два n-значных числа, где n может быть от 100 до 1000.
Подскажите, пожалуйста, алгоритм выполнения.

Автор: Romikgy 3.10.2006, 22:08

если числа представлены строкой, тогда
1. сравнить по длинне строк
2. сравнить по первому символу
3. сравнить по 2 символу
и т.д.

переходы между пунктами если ответ сравнения , равны

Автор: maxim1000 3.10.2006, 22:09

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

Автор: rash 3.10.2006, 22:18

Цитата

если они разные - они и определяют, какое число больше

И этой проверки достаточно, чтобы сказать, что строка string1 больше строки string2

Автор: Romikgy 3.10.2006, 22:23

rash, уточнять надо какое именно сравнения те надо
а вообще может и сказать , все равно имхо везде так делается

Автор: rash 3.10.2006, 22:50

Цитата

уточнять надо какое именно сравнения те надо

Имеется ввиду сравнение как между 5 и 2, т.е. какое из представленных длинных чисел больше.

Автор: Romikgy 3.10.2006, 23:04

Цитата(rash @ 3.10.2006, 21:50

)

Имеется ввиду сравнение как между 5 и 2, т.е. какое из представленных длинных чисел больше.

дык можно сравнивать равно или не равно!

че ответ не подошел который дали?
сравнивай поразрядно , от старшего , но больше меньше

Автор: maxim1000 3.10.2006, 23:47

Цитата(rash @ 3.10.2006, 21:18

)

И этой проверки достаточно, чтобы сказать, что строка string1 больше строки string2

но небольшое замечание: я предполагал, что длины обоих чисел одинаковые (т.е. дополнено нулями по необходимости), если разные - то, конечно, надо смотреть на длины чисел (точнее, длины их значащих частей, т.е. игнорируя нули в старших разрядах)

Автор: esperant0 4.10.2006, 06:58

можно использовать вероятностный алгоритм

Автор: maxim1000 4.10.2006, 11:11

Цитата(esperant0 @ 4.10.2006, 05:58

)

можно использовать вероятностный алгоритм

а поподробнее?
а то интересно...

Автор: rash 4.10.2006, 17:43

Очень интересно.
Как с помощью этого алгоритма сравнить, предположим, два 400-разрядных числа.

Автор: esperant0 4.10.2006, 18:46

Вероятностный алгоритм:

1) стороны случайно равновероятно выбирают лог(х) битов числа и передают эти биты и их индексы друг-другу если все совпало ответ да, числа идентичны, иначе ответ нет.

Автор: Silent 5.10.2006, 16:11

"Вероятностный метод" - а если будут строки "11001..." и 10010..." и выберем n-3-й разряд? Никакого другого способа, кроме лобового использовать нельзя.
Пусть длинное число хранится стандартным способом. Тогда сравнение будет выглядеть так (C++):
bool equal(int[] a, int[] b){
  if (a[0]!=b[0]) return false;
  else {
    int i=a[0];
    while ((i>0)&&(a[i]==b[i])) i--;
    return (i==0);
  }
}

или Pascal:
Function equal(a,b:myar):boolean;
  var i:integer;
  begin
    if a[0]=b[0] then equal:=false
    else begin
      i:=a[0];
      while (i>0)and(a[i]=b[i]) do dec(i);
      equal:=i=0;
    end;
  end;

Автор: esperant0 5.10.2006, 18:55

Цитата(Silent @ 5.10.2006, 16:11)

"Вероятностный метод" - а если будут строки "11001..." и 10010..." и выберем n-3-й разряд? Никакого другого способа, кроме лобового использовать нельзя.

Уточню.

Пусть необходимо ответить на вопрос две строки идентичны или отличаются в более чем х% мест. Тогда можно использовать вер-й алгоритм.

Но это уже из области "property testing".

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

Тогда сущ-ет красивый вер-й алгоритм, позволяющий минимизировать переданную информацию до логарифма от длины строки.

Автор: Romikgy 5.10.2006, 19:06

rash, определись на каком те это языке надо , и какой формат входных и выходных данных и тогда организуем

Автор: rash 5.10.2006, 22:09

Цитата

rash, определись на каком те это языке надо

Спасибо за содействие.
Реализацию сравнения пишу на C++.

Цитата

, и какой формат входных и выходных данных и тогда организуем

Пользователю предлагается ввести два сверхдлинных числа (длину строки он выбирает сам. Предположим, что строки одинаковые и равны, пусть, 400 знаков), затем, должен последовать ответ, что-то вроде, "Из введённых чисел, число string1 больше string2". примерно так. Хотя, могут быть варианты.
Функция сравнения может возвращать, скажем, число string (которое больше) и разницу этого сравнения (на сколько больше).

ВВод строки, предполагаю, будет не более 500 символов.

Автор: Romikgy 5.10.2006, 23:16

в строках только целые числа правильно, если да то завтра выложу ф_цию сравнения, если кто быстрее не сделает,
кса строки это std::string или char * ?

Автор: rash 8.10.2006, 09:56

Совершено верно, строка (std::string) должна быть представлена целыми цифрами,

Код


std::string digits = "129...478;

Вот, примерно так.

Автор: Romikgy 8.10.2006, 17:48

Код


#include <iostream.h>
#include <string.h>
#include <ctype.h >
int cmp_str( string *s1, string *s2,long l)
{
 long i;
 char c1,c2;
 for (i=0;i<l;i++)
 if ((*s1)[i]!=(*s2)[i])
 {
  c1=(*s1)[i];
  c2=(*s2)[i];
  if (
  isdigit(c1)&&
  isdigit(c2)
  )
  {
  c1-='0';
  c2-='0';
  if (c1<c2)
  return -1;
  else
  return 1;
  }
  else
  return 0xff;
 }
 return 0;
}
int dif_cmp_str( string *s1, string *s2,long l1,long l2)
{
  long i;

  for (i=0;i<l1;i++)
  if (!isdigit((*s1)[i])) return 0xff;
  for (i=0;i<l2;i++)
  if (!isdigit((*s2)[i])) return 0xff;

  for (i=0;i<l1;i++)
  if ((*s1)[0]=='0')
   s1->erase(0,1);
   else break;
   for (i=0;i<l2;i++)
  if ((*s2)[0]=='0')
   s2->erase(0,1);
   else break;

   l1=s1->length();
   l2=s2->length();

   if (l1==l2)
   {
   return  cmp_str(s1,s2,l1);
   }
   else
   if (l1>l2) return 1;
  else
  return -1;

 return 0;
}
int compare_long_int(string *s1, string *s2)
{
 long l1,l2;
 int rt;
 l1=s1->length();
 l2=s2->length();
 if (l1==l2)
 rt=cmp_str(s1,s2,l1);
 else
 rt=dif_cmp_str(s1,s2,l1,l2);

return rt;
}
int main(int argc, char* argv[])
{
       string sx1,sx2;
       int cmp=0;
       sx1="20";
       sx2="00009";
       cmp=compare_long_int(&sx1,&sx2);
       cout<<sx1;
       switch (cmp)
       {
        case 0: {cout<<" = ";break;}
        case 1: {cout<<" > ";break;}
        case -1: {cout<<" < ";break;}
        case 0xff: {cout<<" Error ";break;}
       }
       cout<<sx2<<endl;
       system("PAUSE");
        return 0;
}

Автор: rash 10.10.2006, 23:09

За код сравнения длинных чисел большое спасибо.

есть только, два вопроса:

Назначение функций

Код


int  erase();

Код


system("PAUSE");

Автор: Romikgy 10.10.2006, 23:29

Цитата(rash @ 10.10.2006, 22:09

)

int erase();

удаляет начиная с позиции , н колво символов (у меня в коде убирает ни чего не значащие нули)

Цитата(rash @ 10.10.2006, 22:09

)

system("PAUSE");

просто просит типа Press any key to continue....
некоторые заменяют getchar(); из библиотеки <conio.h> (было в падло еще одну библу подключать)

Автор: rash 12.10.2006, 21:40

Благодарю за помощь в решении этого вопроса.

Автор: Diesel Draft 13.10.2006, 19:26

rash откуда тьі?
просто такая задача недавно звучала у нас.

Автор: rash 14.10.2006, 13:47

если это так, то я пренебрёг поиском по сайту. Сорри.

Если вас не затруднит, укажите, пожалуйста, путь к этой задаче.