Двоичное счисление. Задача

[Asya_inter]

Двоичное счисление. Задача

Подскажите, как решить данную задачу (в паскаль авс)? Указать то число заданного множества целых чисел, в двоичном представлении которого больше всего единиц. И по возможности объясните на словах, что здесь вообще выполняется?

 

[MagentaTiger]

Ну для затравки каждое 10 число можно перевести в двоичное, этому по моему учат еще в школе, классе этак в 7-ом.
Подсказка - каждый бит в двоичном числе переводится в 10 как сумма
2 в степени (позиция бита (считая слева от 0)) умноженная на значение бита,
т.е. 10001010 = 2^0*0 + 2^1*1 + 2^2*0 + 2^3*1 + 2^4*0+2^5*0+2^6*0+2^7*1=
0+2+0+8+0+0+0+128=138
Вам же надо провести обратную операцию, алгоритм примерно следующий:
1. ПеременнаяКолЕдиниц :=0
2. ПерменнаяЧисло:=0
3. Берем число из множества
4. Переводим его в двоичную систему
5. Подсчитывать сколько бит выставлено в 1
4. Если число единиц больше чем в сохранено в ПеременнаяКолЕдиниц,
то ПеременнаяКолЕдиниц :=число единиц, ПерменнаяЧисло:=Число из множества
5. Если не конец множества то к шагу 3
6. Вывести ПерменнаяЧисло

 

[MagentaTiger]

Зы:
Если множество конечно (известна максимальная разрядность в ),то количество единиц в числе можно посчитать упрощенным способом использую операцию побитого И (AND) .
типа
A - целое беззнаковое число из множества (0<A<255)
N := (A and 128)+(A and 64)+(A and 32)+(A and 16)+(A and 8)+(A and 4)+(A and 2)+(A and 1)

 

[Vladimir_S]

Подскажите, как решить данную задачу (в паскаль авс)?

К сожалению, эту дрянь (АВС) у себя не держу, поэтому сделал программу на Turbo. Чтобы перевести в АВС, нужно, во-первых, приляпать сверху Program Tralala_Bububu, во-вторых, заменить всюду LongInt на Integer, а вот в-третьих... Точно не помню, но мне кажется, что в АВС какие-то свои аналоги процедур STR и VAL (перевод числа в строку и строки в число, соответственно), так что это нужно уточнить.

Var
 N,M:LongInt;
 Max,NO:Byte;
 St,SM:String;

Function Dec2Bin(D:LongInt):String;
var
 S1,S2,C:String;
 i,L:byte;
 Q:LongInt;
begin
 Q:=D;
 S1:='';
 repeat
  STR((Q mod 2), C);
  S1:=S1+C;
  Q:=Q div 2;
 until Q=0;
 L:=Length(S1);
 S2:='';
 for i:=1 to L do
  S2:=S2+S1[L-i+1];
 Dec2Bin:=S2;
end;

Function Ones(S:String):Byte;
var
 i,L,P,M:Byte;
 C:String;
 Code:Integer;
begin
 P:=0;
 L:=Length(S);
 for i:=1 to L do
  begin
   C:=S[i];
   Val(C,M,Code);
   if M=1 then Inc(P);
  end;
 Ones:=P;
end;

Begin
 Max:=0;
 Repeat
  Write('Next number (0 to quit): ');
  Readln(N);
  if N>0 then
   begin
    St:=Dec2Bin(N);
    NO:=Ones(St);
    Writeln('Binary: '+St+'    Number of ones: ',NO);
    if NO>Max then
     begin
      Max:=NO;
      M:=N;
      SM:=St;
     end;
   end;
 Until N=0;
 Writeln;
 Writeln('Maximal number of ones (',Max,') is in N= ',M, ' ('+SM+')');
 Readln
End.

 

[Asya_inter]

Vladimir_S, спасибо! А вы можете пояснить, почему там после Writeln '+St+' пишется с плюсами?
А ещё, в первой процедуре переводим числа в строковый тип; Во второй процедуре обратно. А как мы узнаём в каком числе больше единиц? И можно ли сделать, чтобы выводилось это число в десятичном виде?

 

[Vladimir_S]

Vladimir_S, спасибо!

Всегда пожалуйста!

А вы можете пояснить

Могу.

почему там после Writeln '+St+' пишется с плюсами?

Это один из способов вывода цепочки строковых переменных. Например, если Вам нужно вывести подряд строки S1, 'Vasya', 'and', 'Asya', то это можно сделать так: Writeln(S1+'Vasya'+'and'+'Asya') ;

в первой процедуре переводим числа в строковый тип;

Правильно. Только там не процедура, а функция. И не просто в строковый тип, а в двоичную форму. Например, если на входе будет 7, то на выходе - '111'.

Во второй процедуре обратно.

А вот это - абсолютно неверно! Вторая процедура, точнее, функция считает количество единиц в двоичной записи числа. Если на входе строка '111', то на выходе будет число 3. А если '1101', то тоже 3.

А как мы узнаём в каком числе больше единиц?

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

И можно ли сделать, чтобы выводилось это число в десятичном виде?

Так это так и делается.

Вообще мой Вам совет - оттранслируйте и запустите программу. Тогда многое прояснится.

Кстати, сейчас увидел, что вторую функцию можно и попроще сделать, без преобразования каждого символа строки в число. Вот так:

Function Ones(S:String):Byte;
var
 i,L,P:Byte;
begin
 P:=0;
 L:=Length(S);
 for i:=1 to L do
  if S[i]='1' then Inc(P);
 Ones:=P;
end;

А то я там малость перемудрил. Нет, можно и как в первом варианте, ошибок нет, но так проще.

 

[Asya_inter]

Vladimir_S, ещё раз спасибо - теперь многое прояснилось! А я думала, что по условию задачи мы вводим несколько чисел, далее смотрим в каком из них больше единиц в двоичном представлении и выводим на экран уже то число. Значит это не так, да?

 

[Vladimir_S]

Значит это не так, да?

Именно так. Точнее:
вводим числа, пока не введем ноль - на нем всё заканчивается. После ввода каждого числа оно преобразуется в двоичную форму, подсчитывается количество единиц в этой двоичной форме и все три числа (самО число, его двоичная форма и количество единиц) запоминаются в переменных N, St и NO, соответственно. St и NO выводятся на экран. Далее смотрится, не превышает ли количество единиц в двоичной записи (NO) ранее найденное максимальное значение количества единиц (Max). Если превышает, то запоминаем полученные три числа (точнее, число, строку и число), как M, SM и Max. Дальше обрабатываем следующее вводимое десятичное число.
В итоге всего этого у нас остаются параметры M, SM и Max, соответствующие числу, имеющему наибольшее количество единиц в двоичной записи. Их мы и выводим на экран.
P.S. Если чисел, имеющих в своей двоичной записи максимальное количество единиц, было введено несколько, то запоминается и выводится первое из них.

Вот как выглядит экран работающей программы: