Расстоянием между двоичными кодами называется количество несовпадающих двоичных разрядов. Например: 0101101 0010101 р=3 ----------- *** Составить функцию Ro (N1,N2), вычисляющую расстояние между двоичными представлениями её целочисленных аргументов N1 N2
Добавлено через 1 мин. желательно написать самый рациональный алгоритм (язык Delphi консольное приложение)
тот алгоритм на кторый вы дали ссылку мне не очень понятен. Вот мой алгоритм: на вход подается 2 целочисленных числа, переводим каждое в двоичный код и запихиваем в 2 массива. Потом начинаем в цикле сравнивать, если не совпадает то счетчик +1. как вы думаете это рабочий алгоритм? если да то помогите с реализацией пожалуйста!))
Вот прога которую я написал. но она почему то не работает подскажите гда ошибка?
program Project1;
{$APPTYPE CONSOLE} uses SysUtils; type TIntarr=array [1..100] of integer; var q,n1,n2:integer; Function Ras (N1,N2:integer):integer; function Perevod (var n:integer):TIntarr; var s,i,l,k:integer; a,b:TIntarr; Begin k:=0; while N>=1 do begin a[i]:=(N mod 2); N:=(N div 2); I:=i+1; end; l:=i; while i<>1 do begin b[k]:=a[i-1]; i:=i-1; k:=k+1; end; b[l-1]:=a[1]; Result:=b; end; var a1,a2:TIntarr; i,t:integer; begin a1:=Perevod (n1); a2:=Perevod (n2); for i:=1 to 100 do if a1[i]<>a2[i] then t:=t+1; result:=t end; begin Writeln ('vvedi chisla'); REadln (n1,n2); q:=ras(n1,n2); Writeln (q); readln; { TODO -oUser -cConsole Main : Insert code here } end.
Рабочий? Да. Рациональный? Нет... Поскольку речь шла о рациональном изначально, то твой алгоритм я предпочитаю не реализовывать... Там битовые операции, выполняется очень быстро, компактный код, здесь - лишние массивы... Что именно непонятно ТАМ?
Добавлено через 6 мин.
Цитата
она почему то не работает подскажите гда ошибка?
Ошибка - в неинициализированных переменных... I внутри процедуры Perevod чему равен, можно узнать? К какому элементу массива ты обращаешься?
я так понял что на вход подаются 2 числа типа Integer. Как перейти к битам?
Число типа Integer - это 32-битное (для Дельфи) целое, правда? И хранится оно в двоичном коде. Скажем, 12 представлено в памяти как 00000000000000000000000000001100, а 13 - как 00000000000000000000000000001101. Так вот, это все - биты, как ты уже догадался, потому как их ровно 32. Теперь, как получить доступ к отдельным битам: проще всего использовать операцию "Битовый AND", которая берет и делает их побитное "умножение" (ну да, And - умножение, а Or - сложение, так уж повелось): (0 and 0) = (0 and 1) = (1 and 0) = 0, и только если оба бита равны 1, то и результат операции And будет единичным: (1 and 1) = 1...
Еще не догадался, как получить содержимое самого младшего бита в числе? Правильно, надо это число "умножить" на маску, состоящую из всех 0, и одной единицы, в том бите, который мы проверяем... Тогда без разницы, что было в первых 31 битах, там после And-а все равно будут нули, а вот состояние последнего бита, маска которого содержит 1, мы узнаем...
Вот и делаем: 00000000000000000000000000001100 and 00000000000000000000000000000001 = 00000000000000000000000000000000 = 010, то есть в числе 12 младший бит НЕ установлен. А в числе 13 - установлен, поэтому 00000000000000000000000000001101 and 00000000000000000000000000000001 = 00000000000000000000000000000001 = 110.
Теперь о том, что значит
inc(res, (n1 and $1) xor (n2 and $1));
(n1 and $1) - это выявление младшего бита первого числа (n2 and $1) - младший бит второго числа
XOR - еще одна битовая операция, которая возвращает: (1 xor 0) = (0 xor 1) = 1, а при равных битах: (0 xor 0) = (1 xor 1) = 0, то есть, если младшие биты обоих чисел НЕодинаковы, то (n1 and $1) xor (n2 and $1) будет = 1. Если одинаковы - будет равно 0... Ну, и последний этап: просто увеличиваем счетчик на это число, если биты разные, счетчик увеличится на 1, если одинаковые - счетчик увеличится на 0, а значит, ничего не изменится... Это то, что и нужно - подсчитывать - то надо те биты, которые различаются...
Ну, и после того, как младшие биты проверены, надо оба числа сдвинуть вправо, чтобы проверить новую пару бит, это и делается через
n1 := n1 shr 1; n2 := n2 shr 1;
- битовый сдвиг на 1 вправо... Проверяем таким образом все 32 пары бит, и в переменной Res имеем число несовпадающих бит в числах.
Тебе надо почитать о битовых операциях (OR, AND, XOR, NOT, SHR, SHL), если ты действительно хочешь в этом разобраться.
мне если можно то побыстрее) завтра уже сдавать(((
Ну, знаешь, это как-то не наши проблемы. Сам дотянул, а теперь тебе срочно надо... Ну, надо - так разбирайся:
program diff;
{$APPTYPE CONSOLE} uses SysUtils;
const size = 32; type TIntarr=array[1 .. size] of integer;
Function Ras(n1, n2: integer): integer;
function Perevod(n: integer): TIntarr; var i: integer; begin FillChar(result, sizeof(Tintarr), 0); i := 0; while n <> 0 do begin inc(i); result[i] := n mod 2; n := n div 2; end; // все остальное - выброшено, потому что не важен порядок чисел, // если A1 будет "перевернут", то и A2 - тоже, а значит, все будет работать end;
var a1, a2: TIntarr; i: integer; begin result := 0; a1 := Perevod(n1); a2 := Perevod(n2); for i := 1 to size do if a1[i] <> a2[i] then result := result + 1; end;
var n1, n2: integer;
begin Writeln ('vvedi chisla'); Readln(n1, n2); Writeln(ras(n1,n2)); Readln; end.
Вообще-то $ перед числом означает, что это число записано в 16-ричной системе счисления. Здесь можно было бы и просто 1 поставить, но это уже привычка: как только дело касается битовых операций (and/or/xor), я обязательно пишу все числа в 16-ричной с/с.
Цитата
непонятно что вот это за строчка еще
У тебя Хелпа нет что-ли? Это заполнение нулями всей переменной result, начальная инициализация, чтоб там всякий мусор не остался...
Моя функция (ссылка во втором посте) - будет, твоя - нет. Я тебе говорил, что работать надо с битами? Говорил. Вот тебе и результат: моей функции совершенно все равно, положительное число или отрицательное, а твоей - есть огромная разница.
=)) твой вариант несовсем прокатил на экзамене(( препод сказал что он маленько не рационален...ну поставил мне конечно 4,5 =) все равно спасибо большое за помощь! я могу показать где что довести до идеала если интересно
Добавлено через 12 мин. вобщем там не надо было умножать на маску. Было предложено просто сделать операцию XOR над числами N1 и N2 (причем один раз а не в цикле) и посчитать где вылазит 0