Loading...
HPetrov avatar HPetrov 822 Точки

Задача за изпит - Bittris

Здравейте!

От няколко часа си блъскам главата здраво на една задача, която е давана на изпит миналата година на пролетния прием в Телерик. Можете да е намерите тук - Bittris. Решил съм по-голяма част от всички задачи давани на изпит но тази просто кара някои от другите да бледнеят пред нея. Порових се из форума на Телерик и намерих доста решения но всички наблягат на битовите операции. Понеже не съм особено голям техен фен повечето подобни задачи си ги решавам с масиви и страшно ме улесняват по този начин. Искам да попитам има ли някой, които вече да е решавал тази задача и да работи напълно вярно в BGCoder но без да е използвал побитови операции? Ще се радвам на малко насоки и ако е възможно share на source code-а ;) Като си поблъскам още малко и аз главата и е подкарам до някъде ще пусна и линк към моя код.

Edit 1: Успях да го докарам до 66/100 (6 от 9 теста) за сега. До сега се водех по логиката, че "фигурките" са непременно няколко бита един след друг като реални фигурки на Тетрис. Явно не е съвсем така но ще го оставя за утре, че в 3 часа как се пише код вече :D

Edit 2: Повече от 66/100 изглежа не мога на този момент да искарам чрез двумерни масиви. Направих е наново само, че побитово този път и се оказа че е доста по приятно и леко за писане конкретно за тази задача. Спрях се на побитовия метод понеже си работи безупречно и не се сблъсках с толкова много бъгове като матричния метод.

Поука: Някои задачи се решават много по лесно чрез матрици отколкото с побитови операции но си заслужава да се помисли малко и върху логиката за решаване чрез другия метод. Ето го и кода за крайното ми решение.

3
Programming Basics
wartus avatar wartus 152 Точки
Последните задачки на телерик винаги са за битове... няма начин :Д
2
HPetrov avatar HPetrov 822 Точки
Авторските решения да но както на останалите задачи, които съм видял е даже по лесно с масиви отколкото побитови :P Интересува ме дали някои си е изблъскал главата до края да докара задачата по този начин ;)
0
beBoss avatar beBoss 507 Точки
Е това, какво общо имаше с темата? Човека иска решение с масиви, а не пита дали има варянт да не се дават "битовите" задачи.
1
ViValDam avatar ViValDam 15 Точки

Е, и  как се заменя побитова операция с масив , нещо не се връзва ?

доколкото знам там се местят насам натам битове , как ше стане това с масиви и какво общо има ?

по скоро лист ще е отколкото масив или арей

-1
beBoss avatar beBoss 507 Точки
Масив и "арей" са едно и също нещо.
2
HPetrov avatar HPetrov 822 Точки
Местиш битовете по същия начин като с побитови операции. Всеки бит е на определен индекс в матрицата и просто си играеш с индексите
2
ViValDam avatar ViValDam 15 Точки

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

 

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

 

По скоро умножение и деление по степени на 2 използвайте, като ви е страх от битовете.

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

1
Fleshian avatar Fleshian 379 Точки

Здравей колега :)

Аз също я бях блъскал доста тая задача преди извесно време , и като цяло сам упсях да я докарам до към 60/100 или преди да погледна отговора. Като цяло аз също съм решил почти всички задачи давани по изпити през годините и бих казал че от битовите задачи тази и една "Формула Бит 1" ги намирам за най-трудни.

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

1. Създаваме 4 празни масива : int row0[8] ... int row3[8] в които ще запзаваме единиците на "кацналите :D" числа.
2. Трявба да преброим единиците на числото за да знаем колкото точки ще добаваме накрая . Бях измислил един алгоритъм преди врем който не ползва битови операции.

int input = int.Parse(Console.ReadLine());
            int onesCounter = 0;
            for (int i = input; i > 0; i /= 2)
            {
                // if  i = 17 or 1 0001 in binary  
                //     i % 2 = 1 ; i/2 = 8;  onesCounter++;;
                //     i % 2 = 0 ; i/2 = 4;
                //     i % 2 = 0 ; i/2 = 2;
                //     i % 2 = 0 ; i/2 = 1;
                //     i % 2 = 1;  i /2 = 0;  onesCounter++;
                if (i % 2 > 0)
                {
                    onesCounter++;    
                }   
            }

3. Създаваме масив който да съдържа единците и нулите на числото до 8-мия бит защото само него трябва да движим наляво или надясно. Можем да го направим така:

  

int input = int.Parse(Console.ReadLine());
            int inputMirror = input;
            int[] eightBitInput = new int[8];
            for (int i = eightBitInput.Length - 1; i >= 0; i--)
            {
                int zeroOrОne = inputMirror % 2;
                inputMirror /= 2;
                if (zeroOrone == 0)
                {
                    eightBitInput[i] = 0;       
                }
                else
                {
                    eightBitInput[i] = 1;                           
                }
            }
Единиците и нулите ги вкарваме в обратен ред в масива поради това че битовете се броят от дясно на ляво.

4. Тука вече опрях на камък защото нямам никаква представа как ще мръднем стойностите  на масива на ляво или на дясно но ако се сещаш нещо , значи и това ще може.

5. След това съответно сравняваме стойностите на input масива със всеки от масивите за 4те реда. И ако някъде двете сравнени стойности са 1 и 1 значи числото се залепя отгоре и съответно вкарваме , всички стойности от input масива на съответния row масив. Ако пък две единици не се застъпят вкарваме стойностите на долния row масив. Тука има нещо много специфично че ако числото може да влезе в долния ред, трябва да провереми дали може да продължи още на долу и ако може ще трябва да върнем сегашния row масив със старите му стойности.
 
Е до този момент не сме използвали битови операции но мисленето ни пак е в битове. Като цяло сe надявам  успя да ми проследиш логиката, ако има нещо не ясно питай :). На теория звучи добре , но практика кой знае колко бъгове ще изпълзят но това е очаквано . Успех , да я избуташ по начина по който си се хванал.
Поздрави, Деян   :) 


1
HPetrov avatar HPetrov 822 Точки
На 04. като стойностите ти са в едномерен масив можеш да ги движеш на ляво или на дясно със съответните побитови операции >> или << 1, стига да си си направил проверката дали случайно не излиза извън полето цифрата :)
0
anton.boyanov avatar anton.boyanov 40 Точки

Само за "спорта" я реших без да използвам нито една побитова операция. С масиви. Ако все още ти е интересно ще ти я изпратя.

Ако искаш само  жокер ---> използвам двумерен масив за полето от 4 реда и отелно от него едномерен, който ми носи числото(разложено на 0 и 1) докато кацне.

П.С.

И за мен, като начинаещ в програмирането това е най-тудната задача от изпит която съм виждал/решавал.

 

0
HPetrov avatar HPetrov 822 Точки

Ами аз отдавна е пререших побитово вече, защото кода ми с масиви стана мармалад и просто реших да пробвам друг начин. Но да, бих видял и твоето решение щом работи на 100% :)

0
anton.boyanov avatar anton.boyanov 40 Точки

И аз, като теб започнах с масиви но я пререших побитово, защото имах проблем с разминаване на фигурите докато падат надолу. Но после, както написах по-горе "за спорта" се върнах и я реших и по другия начин.

Ето кода BittrisWithoutBits

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.