[Homework] Programming Basics - Operators Expressions and Statements - Problem {20} - Bits Up - Софтуерен университет

[Homework] Programming Basics - Operators Expressions and Statements - Problem {20} - Bits Up - Софтуерен университет

+ Нов въпрос
antonp1p2 avatar antonp1p2 17 Точки

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

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

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

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

1
Основи на програмирането 27/03/2015 10:18:06
KatyaMarincheva avatar 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......)
 
3
27/03/2015 09:17:09
AleksandurSeferinkin avatar AleksandurSeferinkin 335 Точки

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

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

Пазим числата в един масив и ключовият момент е цикъла със стъпките. Започваме от бит номер 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).

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

1
GalyaGeorgieva avatar GalyaGeorgieva 88 Точки

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

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

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

3
KatyaMarincheva avatar 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-ца битовете на абсолютно всяка позиция с изключение на нулевата.

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

2
GalyaGeorgieva avatar GalyaGeorgieva 88 Точки

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

1