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

Asya_inter · 19.05.2015, 17:34

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

MagentaTiger · 19.05.2015, 18:23

Ну для затравки каждое 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 · 19.05.2015, 18:39

Зы:
Если множество конечно (известна максимальная разрядность в ),то количество единиц в числе можно посчитать упрощенным способом использую операцию побитого И (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 · 20.05.2015, 12:00

Цитата:

Сообщение от Asya_inter

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

К сожалению, эту дрянь (АВС) у себя не держу, поэтому сделал программу на 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 · 22.05.2015, 21:24

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

Vladimir_S · 22.05.2015, 22:32

Цитата:

Сообщение от Asya_inter

Vladimir_S, спасибо!

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

Цитата:

Сообщение от Asya_inter

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

Могу.

Цитата:

Сообщение от Asya_inter

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

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

Цитата:

Сообщение от Asya_inter

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

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

Цитата:

Сообщение от Asya_inter

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

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

Цитата:

Сообщение от Asya_inter

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

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

Цитата:

Сообщение от Asya_inter

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

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

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

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

Код:

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 · 23.05.2015, 00:41

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

Vladimir_S · 23.05.2015, 09:27

Цитата:

Сообщение от Asya_inter

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

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

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

19.05.2015, 17:34	#1 (permalink)
Asya_inter Member Регистрация: 12.01.2015 Сообщений: 71 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Двоичное счисление. Задача Подскажите, как решить данную задачу (в паскаль авс)? Указать то число заданного множества целых чисел, в двоичном представлении которого больше всего единиц. И по возможности объясните на словах, что здесь вообще выполняется?

22.05.2015, 21:24	#5 (permalink)
Asya_inter Member Регистрация: 12.01.2015 Сообщений: 71 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Vladimir_S, спасибо! А вы можете пояснить, почему там после Writeln '+St+' пишется с плюсами? А ещё, в первой процедуре переводим числа в строковый тип; Во второй процедуре обратно. А как мы узнаём в каком числе больше единиц? И можно ли сделать, чтобы выводилось это число в десятичном виде? Последний раз редактировалось Asya_inter; 22.05.2015 в 21:30

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

19.05.2015, 17:34
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Полезная для вас информация так же содержится тут Задача Создать двоичное дерево записей Задача на Си Задача с if Задача C++

19.05.2015, 18:23	#2 (permalink)
MagentaTiger Специалист Регистрация: 27.04.2015 Адрес: Москва Сообщений: 1,423 Записей в дневнике: 4 Сказал(а) спасибо: 52 Поблагодарили 53 раз(а) в 16 сообщениях Репутация: 18120	Ну для затравки каждое 10 число можно перевести в двоичное, этому по моему учат еще в школе, классе этак в 7-ом. Подсказка - каждый бит в двоичном числе переводится в 10 как сумма 2 в степени (позиция бита (считая слева от 0)) умноженная на значение бита, т.е. 10001010 = 2^00 + 2^11 + 2^20 + 2^31 + 2^40+2^50+2^60+2^71= 0+2+0+8+0+0+0+128=138 Вам же надо провести обратную операцию, алгоритм примерно следующий: 1. ПеременнаяКолЕдиниц :=0 2. ПерменнаяЧисло:=0 3. Берем число из множества 4. Переводим его в двоичную систему 5. Подсчитывать сколько бит выставлено в 1 4. Если число единиц больше чем в сохранено в ПеременнаяКолЕдиниц, то ПеременнаяКолЕдиниц :=число единиц, ПерменнаяЧисло:=Число из множества 5. Если не конец множества то к шагу 3 6. Вывести ПерменнаяЧисло

19.05.2015, 18:39	#3 (permalink)
MagentaTiger Специалист Регистрация: 27.04.2015 Адрес: Москва Сообщений: 1,423 Записей в дневнике: 4 Сказал(а) спасибо: 52 Поблагодарили 53 раз(а) в 16 сообщениях Репутация: 18120	Зы: Если множество конечно (известна максимальная разрядность в ),то количество единиц в числе можно посчитать упрощенным способом использую операцию побитого И (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)

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070

23.05.2015, 00:41	#7 (permalink)
Asya_inter Member Регистрация: 12.01.2015 Сообщений: 71 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Vladimir_S, ещё раз спасибо - теперь многое прояснилось! А я думала, что по условию задачи мы вводим несколько чисел, далее смотрим в каком из них больше единиц в двоичном представлении и выводим на экран уже то число. Значит это не так, да?