[Homework] Programming Basics - Operators Expressions and Statements - Problem {20} - Bits Up

antonp1p2 17 Точки

[Homework] Programming Basics - Operators Expressions and Statements - Problem {20} - Bits Up

Здравейте, имам явно някакъв проблем с задачата. Гледах решения на колеги, но нито едно не съвпада с моето. Ето и кода ми тук.

Проблемът е че така написана програмата работи идеално ако задам стойност на "n" 2 , но ако задам по-голяма стойност се губи някъде из кода и не променя битовете, които трябва.

Някой ако може да ми каже къде съм сбъркал ще съм му много благодарен.

Тагове:

26/03/2015 18:03:22 Programming Basics 27/03/2015 10:18:06

KatyaMarincheva 572 Точки

Здравей Антоне,

Като идея много неща в подхода ти към решението ме заинтригуваха, но съм твърде разсеяна и не можах добре да проследя всеки етап от логиката на кода - много последователни и едновременни промени - и съжалявам че не го рабрах защото по принцип много обичам задачи с побитови оператори.

Аз опитах да използвам обаче доста елементи от твоя подход:

* идеята да търсиш позициите, на които битовете трябва да се променят, по цялата дължина на получения инпут

* идеята да събираш числата в int[] масив, и т.н.

и така да се каже, с твоя помощ си направих мое решение, което дава 100 точки:

1. превръщам всичките N въведени числа в двоична бройна систтема, от по 8 бита, и ги свързвам в един дълъг стринг общ за всичките N числа

// StringBuilder binaries will be storing the binary representation of all n numbers

StringBuilder binaries = new StringBuilder();

// for all n numbers read from the console

for (int i = 0; i < n; i++)

{

number = int.Parse(Console.ReadLine()); // read the number

string bin = Convert.ToString(number, 2).PadLeft(8, '0'); // convert the number to a binary string

binaries.Append(bin); // append the above binary string to StringBuilder binaries

}

2. в този бинарен стринг променям на 1 всеки char, който се намира на позиция 1, 1 + step, 1 + 2*step, ...

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

3. нарязвам бинарния стринг на substrings от по 8 char-a, и ги превръщам във final int numbers

Ето и целия код: http://pastebin.com/aP9c6F6C (с comments overkill......)

26/03/2015 22:21:19 27/03/2015 09:17:09

AleksandurSeferinkin 333 Точки

Колега, твърде сложно си го направил и няма смисъл да се мъчиш да го поправяш, а просто да го пренапишеш.

Ето ти едно по-опростено решение тук.

Пазим числата в един масив и ключовият момент е цикъла със стъпките. Започваме от бит номер 1 и въртим до n * 8.

След като знаем кой бит трябва да променим и знаем, че числата в масива имат по 8, можем да разберем кое число от масива ни трябва.

Като разделим моментния бит на 8, ще получим резултат, който ни е необходим да разберем с кое число в масива ще работим. Обаче това не винаги ще върне резултат цяло число - затуй ползваме Math.Floor.

След като знаем с кое число от масива работим, ще ни трябва да разберем кой бит от числото да променяме. Това се намира с модул - int bitIndex = currentBit % 8. Така винаги ще получаваме числа от 0 до 7. В условието пише "Bits in each byte are counted from the leftmost to the rightmost.". В компютъра битовете са наобратно. Затуй правим така int bitIndex = 7 - (currentBit % 8).

Променянето става елементарно с маска.

27/03/2015 00:01:52

GalyaGeorgieva 88 Точки

Моето решение е доста кратко, но също работи.

Аз използвам два вложени цикъла. С първия "въртя" числата, а с втория "въртя" битовете. Логиката е: имам брояч на всички битове на всички числа (n*8) и ако бит-ът е == 1 или 1+step, 1+2*step и т.н. (брояч % 2 ==1) да се превърне в 1. "Закачката" е, че вторият цикъл брои наобратно, т.е. от 7 до 0 и така знам позицията, която да "ударя" с единица.

Кодът можете да видите ТУК

27/03/2015 11:00:24

KatyaMarincheva 572 Точки

Здравей Галя,

това решение е наистина много, много по-кратко и елегантно, и за да даде пълните 100 точки в judge има нужда от една малка добавка:

От една страна counterBits % step == 1, всъщност обхваща случая counterBits == 1, защото например 1 % 4 = 1

Случаят, който допълнително е необходимо да се обхване, е когато step = 1, защото за всяко число ще е вярно

number % 1 = 0; и никога няма да има bits-up-ване на която и да било позиция.

По тази причина авторското решение добавя още едно изискване:

if ((index % step == 1) || (step == 1 && index > 0))

В случая (step == 1 && index > 0) ще променяме на 1-ца битовете на абсолютно всяка позиция с изключение на нулевата.

Може да тестваш тук

27/03/2015 11:52:20

GalyaGeorgieva 88 Точки

Благодаря, за допълнението. Бях забравила за това изключение и сега всичко е точно :)

27/03/2015 12:57:38