Broadcom 4312 in Arch Linux
Hi all.
Finally, I’ve configured my Broadcom 4312 Wireless card in Arch Linux and can write something about this now.
First, you should determine the name of your card. Try to do
lspci | grep Broadcom
to see, what you have. You should see something like
04:00.0 Network controller: Broadcom Corporation BCM4312 802.11b/g LP-PHY (rev 01)
if you have Broadcom4312.
Also see what kernel do you have:
uname -r
All described below should work for 2.6.39-ARCH.
Also, I assume that you have internet already (or at least have access to the internet from other computer).
Go to this link http://www.broadcom.com/docs/linux_sta/README.txt and follow that instruction.
You should download source code of the driver, apply a patch and then compile it.
(should I write more detailed information here?)
After this, you will have file ‘wl.ko’.
Then unload from kernel some modules:
rmmod b43 rmmod ssb rmmod wl
and load others:
modprobe lib80211 insmod wl.ko
then see, what is the name of the interface for you wireless card:
ifconfig -a
and up that interface:
ifconfig eth1 up
After this configure your connection.
Probably you should read about WPA_supplicant.
In my case, I’ve edited file /etc/wpa_supplicant.conf and run
wpa_supplicant -B -Dwext -i eth1 -c /etc/wpa_supplicant.conf
then you probably should do (if you have dhcp)
dhcpcd eth1
and you have internet, finally.
Из стенфордской лекции
//подсмотрено из стенфордской лекции
#include <stdio.h>
int main(){
int arr[4];
int i;
for (i=0; i<=4; i++){
printf("%i\n", i);
arr[i]-=4;
}
return 0;
}
Вопрос: что выведет программа?
Указатель на константу?
Я уже говорил об этом в прошлом посте, а теперь более конкретно.
Допустим, есть такой код:
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
const int i = 7;
const int *cpi = &i;
int *pi = (int*)(void*)cpi;
printf(" &i = %x\t i = %i\n",&i,i);
printf(" cpi = %x\t *cpi = %i\n",cpi,*cpi);
printf(" pi = %x\t *pi = %i\n",pi,*pi);
*pi = 3;
printf("\n\n\n");
printf(" &i = %x\t i = %i\n",&i,i);
printf(" cpi = %x\t *cpi = %i\n",cpi,*cpi);
printf(" pi = %x\t *pi = %i\n",pi,*pi);
return 0;
}
Если этот код скомпилировать и выполнить, то вывод будет следующим:
&i = 22ff44 i = 7 cpi = 22ff44 *cpi = 7 pi = 22ff44 *pi = 7 &i = 22ff44 i = 7 cpi = 22ff44 *cpi = 3 pi = 22ff44 *pi = 3 Process returned 0 (0x0) execution time : 0.016 s Press any key to continue.
Коротко о переменных:
i – просто целочисленная переменная,
cpi – указатель на целочисленную константу,
pi – указатель на целочисленную переменную.
Судя во всему, cpi (указатель на константу) на самом деле указывает не на константу. Изменение значения по адресу cpi блокируется компилятором на уровне синтаксиса, но во время выполнения значение по этому адресу все-таки можно изменить.
Почему же i и *cpi в итоге разные, если &i и cpi одинаковые – для меня загадка. Свои догадки писать здесь не буду, а то кто-то прочитает и будет думать, что это правда 
Избитая тема про музыку вконтакте
Вообще уже настало время, когда хранить музыку на винчестере смысла особого нет.
Но, блин, с инетом проблемы бывают. Поэтому пусть пока лучше будет
Итак, как сохранить свою музыку с сайта вконтакте на свой компьютер?
Если посмотреть код страницы «Аудиозаписи», то можно заметить, что код разбит на div’ы, span’ы и тд, что позволяет легко вычленить ссылки на mp3-шки и получить сведения о песне (название, группа). И сохранить с нормальными названиями, а не просто комбинациями цифр и букв.
Кажется, что все просто, но это не так.
У меня 173 аудиозаписи, это все разбито на 2 страницы (100 штук на первой, остальное на второй).
Когда я перехожу на вторую страницу – в исходнике ничего не меняется. Ничего страшного, конечно, но просто остаются те же 100 песен, что были на 1-й странице.
Хаха, не трудно догадаться, что здесь замешан так горячо любимый мною JavaScript.
В Opera можно легко отключить javascript, после чего переход на вторую страницу позволяет просмотреть ее исходный код и увидеть оставшиеся 73 песни.
Структура кода примерно такая:
... <div class="audioRow" id="audio84309192"> <a name='84309192'></a> <table width="100%"><tbody> <tr><td style="width: 20px; vertical-align:top"> <img class="playimg" onclick="return operate(84309192,'http://cs4707.vkontakte.ru/u12848345/audio/e7bffd8f5682.mp3',281);" id="imgbutton84309192" nosorthandle="true" src="images/play.gif"/> </td> <td style="width: 360px;"><div class="audioTitle"> <b id="performer84309192"><a href='gsearch.php?section=audio&c[q]=Queen'>Queen</a></b><span> - </span><span id="title84309192"><a href='javascript: showLyrics(84309192,4589379);'>I Want It All</a></span> </div> <div class="duration">4:41</div> </td> </tr> </tbody></table> <div style="height:14px;margin-left:28px;"> <div id="line84309192" class="playline"></div> <div id="toddler84309192" class="toddler"> </div> <div id="player84309192" style="display: none;" class="playerClass"> </div> </div> <div id="lyrics84309192"></div> </div> <div class="audioRow" id="audio81408147"> <a name='81408147'></a> <table width="100%"><tbody> <tr><td style="width: 20px; vertical-align:top"> <img class="playimg" onclick="return operate(81408147,'http://cs4718.vkontakte.ru/u59481183/audio/c3ff1145f6ec.mp3',146);" id="imgbutton81408147" nosorthandle="true" src="images/play.gif"/> </td> <td style="width: 360px;"><div class="audioTitle"> <b id="performer81408147"><a href='gsearch.php?section=audio&c[q]=Валерий Горбачев'>Валерий Горбачев</a></b><span> - </span><span id="title81408147">До первого убитого</span> </div> <div class="duration">2:26</div> </td> </tr> </tbody></table> <div style="height:14px;margin-left:28px;"> <div id="line81408147" class="playline"></div> <div id="toddler81408147" class="toddler"> </div> <div id="player81408147" style="display: none;" class="playerClass"> </div> </div> <div id="lyrics81408147"></div> </div> ...
Отличие между этими двумя песнями в том, что для первой есть слова, а для второй – нет.
Таким образом, в Song! может внутрь вставляться гиперссылка и тогда получается
Song!
.
Уже зная это можно написать программу на любом тьюринг-полном.
Я написал скрипт на Ruby. Работать с ним надо так:
- Поместить его в папку, куда должны скачиваться файлы
- Сохранить в эту папку файлы страниц вконтакте с ссылками на аудиофайлы
- Запустить скрипт, ввести имена данных файлов
- Подождать
Вот, что было у меня:
Можно заметить, что есть несколько песен, скачанных с ошибкой:
причем первая песня была недоступна с сервера (не проигрывалась даже на самом контакте), а вторая судя по всему содержала запрещенный символ в названии.
Думаю, результат можно считать удовлетворительным.
Вот мой скрипт:
#script helps you to download music
#author jtim, 17 august, 2010
#email jtimchenko@gmail.com
require 'rubygems'
require 'hpricot'
require 'iconv'
require 'open-uri'
def download_file(link, filename)
begin
writeOut = open(filename, 'wb')
writeOut.write(open(link).read)
writeOut.close
rescue
return false
end
true
end
utf8 = Iconv.new("utf8", "windows-1251")
links = Hash.new
re_link = Regexp.compile("'(.*)'")
re_song = Regexp.compile("<.*?>")
loop{
puts"Enter name of file to scan or empty line to start downloading..."
input_file_name = gets.chomp
break if input_file_name == ""
begin
(Hpricot(open(input_file_name))/'div.audioRow').each do |nd|
begin
fn = re_link.match((nd/'img')[0]['onclick'])[1]
artist = utf8.iconv((nd/'a')[1].inner_html())
song = utf8.iconv((nd/'span')[1].inner_html()).gsub(re_song,'')
links[fn] = artist + " - " + song+'.mp3'
rescue
puts "Error!"
puts nd.to_html
puts "-----"
end
end
rescue
puts "Error while opening file!"
end
links.each_key{|k|
puts k+" : "+links[k]
}
puts "There are #{links.length} files in list!"
}
all = links.length
num = 1
links.each_key{|k|
print("downloading [#{links[k]}]: #{num} / #{all} : ")
msg=''
if download_file(k, links[k])
msg='OK'
else
msg='ERROR!'
end
puts(msg)
num+=1
}
Что надо отметить:
- Это работает для ruby 1.8. На ruby 1.9 я не проверял
- Используется gem hpricote для парсинга html файла – код библиотеки написан самим Why (автор книги why’s poignant ruby guide)
- Я заюзал регулярки, нифигасе!
Основные минусы:
- Появляются символы типа «Vicky Leandros – Tango d'Amor.mp3″. Конечно же там должен стоять апостроф. Видимо, это возникает при переводе cp1251 в utf8.
- Каждый файл скачивается за раз. Пока он не скачался полностью – ничего не сохранено. Как только файл скачается целиком – он сразу же будет записан на винт. Короче, если интернет часто обрывается, то скрипт становится почти бесполезным.
Основные плюсы:
- Простота в использовании
- Человеческие имена файлов
- Теперь можно будет слушать музыку, не заходя на контакт!
p.s.: в посте есть парочка несмертельных ошибок, но исправлять сейчас уже нет сил. Надо бы поспать)
Processing
Processing – это язык программирования для быстрого создания демонстраций. Ну или что-то типа того.
Он основан на java и может использовать все, что написано на java.
Созданные приложения можно экспортировать в веб-страничку с java-апплетом. Тогда код на Processing переводится на java.
После неудачной попытки сделать что-то красивое и полезное на javascript я решил попробовать processing.
Кончилось это тем, что я сделал небольшой sketch (зарисовка, в processing так называются проекты).
Он посвящен вставке элементов в бинарное дерево поиска.
А вот и видео: Binary search tree insertion demo
Все это заняло около 170 строк кода. По-моему, вполне лаконично.
UPD. Теперь я хочу сделать еще какую-нибудь визуализацию. Например, red-black-tree, AVL-tree. А может быть еще какую-нибудь структуру данных (типа дерева Фенвика, дерева отрезков или системы непересекающихся множеств).. Или даже алгоритм сортировки какой-нибудь.
Меня очень впечатлило это видео со сравнением QuickSort и BubbleSort и мини-соревнованием в конце : video
Про поиск
Привет.
Что надо делать, если в данном тексте T (text) надо найти строку P (pattern) ?
Варианты:
- Тупой поиск в лоб
- Чуть-чуть более умный поиск (алгоритм Рабина-Карпа), где-то в челюсть
- Поиск на основе конечных автоматов (пусть будет в пупок).
- Модифицированный поиск на основе КА: Алгоритм Кнута-Морриса-Пратта. Да-да, как раз туда.
- Есть еще много-много способов найти что-то в чем-то, например, алгоритм Ахо-Корасик и другие устрашающие комбинации фамилий
Если строка и текст довольно небольшие (пусть до 50 символов) – можно смело использовать первый вариант.
Но лучше даже в такой ситуации применить алгоритм Рабина-Карпа и быть спокойным.
Для более тяжелых случаев понадобится конечный автомат.
Чуть подробнее: мы строим для данного образца конечный автомат.
Состояния обозначаются номерами от 0 до m (длина образца). Если автомат находится в состоянии i, значит на данный момент совпало i символов образца и послендих i символов текста.
Понятное дело, перед поиском надо построить таблицу переходов.
Ну и в конце концов – само совершенство – алгоритм Кнута-Морриса-Пратта.
О нем все так много говорят! Иногда мне даже кажется, что я единственный человек на Земле, который не понял его!
Конечно, я решил исправлять ситуацию. Но, черт возьми, никак не могу врубиться, откуда свалилась эта префикс-функция? Как авторы вдруг догадались ее использовать?
Если вы оказываетесь в подобной ситуации, лучшим выходом будет просто открыть Кормэна, найти, прочитать и понять нужную главу, а потом выполнить упражнения. Если вы не смогли выполнить эти упражнения – значит вы не нашли нужную главу, или не прочитали ее. Ну или не поняли. Но как правило понимание приходит во время решения упражнений.
Есть небольшая деталь. Очень эффективно применять КА или КМП, если есть один шаблон и много текстов. Фактически один раз мы строим таблицу переходов, а потом просто просматриваем тексты за 1 проход и знаем количество вхождений и их «координаты».
Интереснее другое. Что, если образцов много, а текст – один?
Ну, например, решили выяснить – кто же все-таки отец (из этих 30) данного человека? Я правда не знаю, может там и не поиск подстроки…
Все эта каша-малаша возникла у меня в голове, когда я пытался решить эту задачу:
http://codeforces.com/contest/25/problem/E
А потом я решил сделать еще кое-что.
Вот скриншот (не знаю, где есть нормальный хостинг, чтобы выложить это):
Конечный автомат для поиска образца в тексте
Сделал я это на JavaScript. Для вывода графов использовал какой-то глючный минифреймворк dracula, на который даже ссылку давать не хочу.
Я еще давно понял, что мы с JavaScript созданы не друг для друга. Так что спешу перечислить основные минусы JavaScript:
- Это не Ruby и даже не C++
- Какие-то странные приколы с переменными.
var a = 3; b = 2; delete b; // можно, удаляется созданное нами же свойство объекта window delete a; // нельзя, пытаемся удалить переменную
- Пусть есть строка a. Не знаю, почему, но у меня a[i] не ратало. Пришлось делать a.charAt(i)
- Непонятная ситуация с массивами. Например, такой код у меня не работал так, как я ожидал:
var a = [1,2,3]; for (i in a) alert(i);
Надо делать так:
var a = [1,2,3]; for (i in a) alert(a[i]);
По-моему, довольно странно. Я же не объявлял массив как ассоциативный массив !
К этому надо прибавить невозможность нормальной отладки и разные реакции браузеров на один и тот же код. И да, эта конченая библиотека для рисования графов. Она не позволяет изменять или перерисовывать графы. Формируй граф до загрузки страницы – и никак иначе!
Резюме.
javascript – это совершенно отличный от C++ язык, взять хотя бы прототипы и замыкания.
Поиск подстроки в строке – интересная задача, имеющая не менее интересные алгоритмы решения, в том числе Рабина-Карпа, Ахо-Корасик, конечный автомат, КМП и так далее.
Как нарисовать стрелку
Лично у меня такая задача возникала не один раз, поэтому придется посвятить ей целый пост.
Итак, даны координаты начала и конца вектора, надо нарисовать стрелку.
Результат будет вот такой:
А теперь к тому, как собственно рисуется стрелка. Чертеж, сделанный в paint (кликабельно):
Пусть исходный отрезок AB.
Повернем точку B вокруг точки A на alpha и на -alpha. Укоротим полученные векторы так, чтобы их длина составляла M (M <= 1) от длины вектора AB. Тогда получим векторы AC и AD.
Соединим точки A и B, B и C, B и D отрезками – стрелка нарисована.
Теперь как это выглядит конкретно на C++ и SFML:
void RotatePoint(double &x, double &y, double ox, double oy, double alpha)
{
double xn, yn;
xn = ox + (x-ox)*cos(alpha) - (y-oy)*sin(alpha);
yn = oy + (x-ox)*sin(alpha) + (y-oy)*cos(alpha);
x = xn;
y = yn;
}
void DecreaseVector(double x1, double y1, double &x_n1, double &y_n1)
{
double dx = (x_n1 - x1)*0.9;
double dy = (y_n1 - y1)*0.9;
x_n1 = x1 + dx;
y_n1 = y1 + dy;
}
void SFMLVizualizer::DrawArrow(int x1, int y1, int x2, int y2, int icolor)
{
int red, green, blue;
blue = icolor%255;
icolor/=255;
green = icolor%255;
icolor/=255;
red = icolor;
sf::Color color = sf::Color(red, green, blue);
int line_width = 1;
w->Draw(sf::Shape::Line(x1, y1, x2, y2, line_width, color));
double x_n1, y_n1, x_n2, y_n2;
x_n1 = x_n2 = x2;
y_n1 = y_n2 = y2;
RotatePoint(x_n1, y_n1, x1, y1, pi/48);
RotatePoint(x_n2, y_n2, x1, y1, -pi/48);
DecreaseVector(x1, y1, x_n1, y_n1);
DecreaseVector(x1, y1, x_n2, y_n2);
w->Draw(sf::Shape::Line(x_n1, y_n1, x2, y2, line_width, color));
w->Draw(sf::Shape::Line(x_n2, y_n2, x2, y2, line_width, color));
}
Такие стрелочки имеют свойство масштабироваться в зависимости от длины вектора. Выглядит очень симпатично, я даже сам не ожидал такого!
Debug me!
Вы же знаете, что такое Crack me? Ну, я уверен, что все даже игрались когда-то. Как там, берем Crack me #2 (потому что #1 уже одолели), открываем в IDA Pro Disassembler и вперед… Исправляем JNE на JNZ или что-то в таком духе.
А недавно я видел человека, который писал игру «Дурак» на C++ с использованием классов.
И все было бы прекрасно, если бы не один глюк.
Сначала кажется, что глючим мы – когда пишем код. Но потом мы ищем ошибку и не находим ее. Потом ищем еще раз – и опять не находим! Очевдно, что глючим не мы. Глючит компилятор, операционка, клавиатура, все, что угодно – только не мы. Потому что код просмотрен и проверен уже 100 раз!
На этот раз глючила колода. Я не шучу. Не помню деталей, но по-моему колода имела метод
Card Deck::GetCard()
который возвращал из колоды карту.
Удивительно, но после раздачи 6 карт компьютеру и 6 карт человеку в колоде оставалось то 24, то 23 карты. Причем чаще 24.
Отладка происходила довольно тупым способом. Сперва повесили printf()’ы сразу после { и перед }, в которых выводили все, что могло принести какую-то пользу: количество карт в колоде, карты на руках у игроков.
Потом додумались до «инварианта цикла», круто?
Прям в лучших традициях Кормэна! Суть в том, что deck.cards_count() + player1.cards_count() + player2.cards_count() == 36 всегда.
Таким образом повесив if (…) мы дали программе возможность самой определять, произошла ли ошибка.
Потом пришлось все-таки делать обертки из printf()’ов еще для нескольких фукнций. В итоге определилось место ошибки (точно функцию не помню, но смысл такой же) :
bool Card::Exists()
{
return this->num > 0;
}
Ошибка в num > 0 (надо было num >= 0).
По-моему, очень глупая ошибка. Связанная с невнимательностью и нетривиальной задумкой по поводу хранения карт в колоде.
Нет бы сделать List <Card> или Vector <Card>, так нет блин… )))
Но сам процесс отладки лично мне доставил удовольствие и вот, что я подумал.
А вдруг, кто-то, найдя очередную подобную ошибку, не просто исправит ее, а запишет, запомнит и потом на основе ее сделает «Debug me!».
Да и вообще, сделать бы сайт для программистов. Куча мелких программ, в каждой какая-то ошибка, которую надо исправить! Вау.
Идея утопическая, конечно, потому что дай только такому сайту появиться – сразу студенты запостят свои лабы.
Delta-wave (Timus 1302)
А теперь я заберу у вас кайф, потому что если вы продолжите читать дальше, то уже не сможете решить эту задачу сами, потому что я сам расскажу вам, как это сделать. Если что, лучше попробуйте сами, а потом читайте этот пост до конца.
Задача
Кому не нравится английский, там же есть и русская версия (слева сверху «RU»).
А теперь решение.
Для начала, нарисуем граф, в котором вершины будут хранить натуральные числа и между двумя вершинами будет ребро, если в исходной пирамидке эти два числа были разделены 1 ребром треугольника. Более того, расположим этот граф определенным образом на плоскости, так, чтобы каждая вершина имела вполне определенные координаты по x и по y.
Получится что-то вроде такого:
Посоветуйте плиз нормальный графический редактор, а то много сил уходит на рисование в paint.
Для данных двух чисел находим их координаты, или, по-другому, столбец и строку, в которых находится каждое из чисел.
Допустим, vert_moves = | row_m – row_n | – это модуль разности номеров строк этих чисел, а hor_moves = | col_m – col_n | – аналогично для столбцов.
Очевидно, что для попадания из вершины с 1-ым числом в вершину со 2-м числом надо сделать как минимум vert_moves ходов. Но этого может оказаться недостаточно. Например, для чисел 27 и 9 – за 5 ходов мы можем попасть из 27 в 5 и надо еще 4 хода, чтобы попасть из 5 в 9.
Некоторые вертикальные ходы будут совмещаться с горизонтальными (в силу структуры графа), например, ходы из 10 в 11, из 17 в 18, из 21 в 22, из 34 в 33 и так далее.
По количеству вертикальных ходов мы можем определить, сколько из них могут быть одновременно и горизонтальными. Если мы идем из вершины с нечетного ряда и в вершину нечетного ряда, то по пути мы сделаем vert_moves/2 горизонтальных ходов (пока не важно, в каком горизонтальном направлении будет каждый из этих шагов).
Такая же ситуация, если идем из вершины четного ряда в вершину четного ряда.
Если путь из вершины нечетного ряда в вершину четного, то количество горизонтальных шагов будет таким же, как в пути из вершины следующего после нечетного ряда (таким образом, четного) в четный. Например, ищем путь из вершины 6 в вершину 17. 6 находится во 3-м ряду, а 17 – в 8-ом.
Тогда кол-во горизонтальных шагов в этом пути такое же, как и из 2 ряда в 8. А это мы уже умеем считать – (8-2)/2 =3 хода.
И, наконец, если путь из вершины четного ряда в вершину нечетного (скажем, из вершины 11 в вершину 23). Тогда кол-во горизонтальных шагов равно пути из предыдущего нечетного ряда в вершину четного. Для вершин 11 и 23 это значит, что кол-во горизонтальных ходов не изменится, если вместо вершины 11 взять вершину 5, 7 или 9.
Итак, теперь мы знаем количество горизонтальных и вертикальных шагов, которые мы должны сделать и так же количество горизонтальных ходов, которые можем сделать, пока будем делать вертикальные ходы. Пусть это будет may_hor.
Если may_hor<hor_moves, то придется сделать дополнительно hor_moves-may_hor ходов, а ответ будет vert_moves + hor_moves – may_hor.
Теперь о том, как вычислить координаты числа x.
Нетрудно заметить, что если число является полным квадратом, то его координата x – это sqrt(x)-1 (номер столбца), а координата y – это (sqrt(x)+2)/2 (номер строки).
Если число не является полным квадратом, то найдем для него ближайшее большее число, которое является полным квадратом, пусть это будет sq. Если четности числа и sq совпадают, то они находятся в одной строке. Если не совпадают, то строка для числа на 1 меньше, чем строка для sq.
Столбец для числа считается просто – это столбец для sq минус разницу между числом и квадратом.
Т.е. col_number = col_sq – (sq – number).
Вот, в принципе и все. Но есть одно НО. Я получил.. нет, не Wrong Answer и не TLE, а Compilation Error! o_O
У меня, правда, все компилировалось (gnu gcc compiler). Ошибка была связана вот с чем:
long x; double t = (long)sqrt(x);
Компилятор не знал, какую из sqrt выбрать – sqrt(float), sqrt(double) или sqrt(long double).
Ну и напоследок программа, которая получает Accepted:
//file main.cpp, task 1302
#include <iostream>
#include <math.h>
void find_coords(long x, long &x_col, long &x_row)
{
// ищем наименьшее число, большее либо равное x, являющееся полным квадратом
double t = (long)sqrt((double)x);
long sq = t*t;
long sq_less = (t-1)*(t-1);
if (sq < x)
{
t++;
sq = t*t;
sq_less = (t-1)*(t-1);
}
// ищем номер строки, в которой будет находиться x
x_row = (t-1)*2;
if (x%2 != sq%2)
x_row--;
long sq_col = t-1; // столбец, в котором будет находиться sq
x_col = sq_col + x - sq; // столбец, в котором будет находиться x
}
// сколько ходов в сторону можем сделать, добираясь со строки row1 в row2
long may_hor_moves(long row1, long row2)
{
if (row2<row1) return may_hor_moves(row2, row1);
if (row1%2 == row2%2)
return (row2-row1)/2;
if (row1%2==1)
return (row2-row1+1)/2;
return (row2-row1-1)/2;
}
int main()
{
long N, M, col_m, row_m, col_n, row_n;
std::cin >> N >> M;
if (N>M)
{
long t = N;
N = M;
M = t;
}
find_coords(N,col_n,row_n);
find_coords(M,col_m,row_m);
long vert_moves = abs(row_n - row_m);
long hor_moves = abs(col_n - col_m);
long add_moves = may_hor_moves(row_n, row_m);
long ans = vert_moves;
if (hor_moves > add_moves)
ans += (hor_moves - add_moves);
std::cout << ans << std::endl;
return 0;
}
Accepted, время работы 0.015, используемая память 217 КБ.
Машины с натуральнозначными регистрами
Прощай, матлогика, здравствуй, теория алгоритмов! Правда, это те же яйца, только в профиль.
Я еще заранее решил, что перейду в другую подгруппу, потому что там вела няшная девушка. Она, в принципе, мало чего могла объяснить (в основном фразы вроде «Это так, потому что так написано в методичке лектора»), но какая нафик разница – лектора понять в принципе невозможно.
Облом. Вести теперь будет парень.
Зато он объясняет, причем все понятно, простым русским языком, как для дебилов. Я этому очень рад
Итак, машина с натуральнозначными регистрами, она же МНР.
Это гипотетический дивайс, который имеет бесконечное множество регистров (но, тем не менее, счетное), пронумерованных, начиная с 0: 0, 1, 2, …, N, N+1, … , в каждом из которых может храниться любое натуральное число. Также машина умеет выполнять программы, записанные в виде последовательности команд, которые нумеруются с 1.
Перед началом работы мы задаем начальную конфигурацию МНР – значения регистров.
В процессе работы, МНР что-то делает с содержимым регистров. В итоге она либо останавливается (и тогда мы читаем результат в регистре R[0]), либо.. не останавливается о_О.
Вообще, задать по очереди значения всем регистрам проблематично (их бесконечно много). Но для каждой МНР в частности мы используем лишь ограниченное количество регистров (по крайней мере, нам так сказали.Но я в это не верю и могу написать программу для МНР, которая таки будет использовать все регистры. Подошел к преподу и выяснилось, что в командах можно использовать только жестко зафиксированные константы, но об этом ниже.)
Поэтому мы даем на вход МНР числа (R0, R1, R2, …, RM) и считаем, что регистры с номерами >M содержат 0.
Т.к. в итоге мы берем результат из R[0], то МНР задает функцию f: Rm->R. Логично, что если результатом считать не только R[0], но вообще некоторое число регистров R[0], … R[N], то можно говорить о том, что МНР задает функцию f: Rm->Rn.
Если сказать правду, то одна МНР задает бесконечное количество функций fq: Rq->Rn, где q = 1, 2, …, W, W+1, … .
МНР понимает 4 команды:
- Z(i): (zero) обнуляет регистр номер i: R[i]=0
- S(i): (successor) увеличивет содержимое регистра номер i на 1: R[i]++
- T(a,b): (transfer) записывает R[b] в R[a]. Куда при этом исчезает старое значение из R[a] – открытый вопрос.
- J(a,b,c): (jump) если R[a]==R[b], то переходит к команде номер c
При этом нельзя использовать косвенную адресацию, т.е. в команде J можно использовать только константы. Нельзя написать что-то вроде J(0,0,R1), чтобы машина перешла в регистр, адрес которого содержится в R1. Жаль, иначе я все-таки смог бы написать программу, которая перебирает все ячейки
Выполнение программы начинается с команды №1 в списке.
После каждой команды идет переход к следующей, в случае команды J – может произойти прыжок куда-нибудь.
МНР завершает работу, когда пытается выполнить команду, номер которой больше, чем команд в программе.
Если фунция f не опредлена для входного вектора (a0, a1, …, aN), то МНР должна зациклиться с такой начальной конфигурацией.
Некоторые примеры МНР.
Для фунции f(x) = x МНР такая:
1) J(0,0,2)
Для функции f(x) = x+2:
1) S(0); 2) S(0);
Для облегчения тестирования МНР, я написал такой модуль:
// file MNR.cpp
#include "MNR.h"
TCommand commands[M];
int R[N];
int step; // number of current step
int steps_count=0;
void vZ(int a){R[a] = 0; step++;}
void vS(int a){R[a]++; step++;}
void vT(int a, int b){R[a] = R[b]; step++;}
void vJ(int a, int b, int c){if (R[a]==R[b]) step=c; else step++;}
void J(int a, int b, int c)
{
step++;
commands[step].type = tJ;
commands[step].a = a;
commands[step].b = b;
commands[step].c = c;
}
void S(int a){step++;commands[step].type = tS; commands[step].a=a;}
void Z(int a){step++;commands[step].type = tZ; commands[step].a=a;}
void T(int a, int b)
{
step++;
commands[step].type = tT;
commands[step].a = a;
commands[step].b = b;
}
void Run()
{
steps_count = step;
step = 1;
while (step <= steps_count)
switch (commands[step].type)
{
case tS: vS(commands[step].a); break;
case tZ: vZ(commands[step].a); break;
case tJ: vJ(commands[step].a,commands[step].b,commands[step].c); break;
case tT: vT(commands[step].a,commands[step].b); break;
}
}
void Input(int arg_c)
{
int arg, i;
for (i = 0; i<arg_c; i++)
{
printf("Enter arg. no. %d\n", i+1);
scanf("%i",&arg);
R[i] = arg;
}
}
void Output(int arg_c)
{
int i;
for (i=0; i<arg_c; i++)
printf("R[%i] = %i\n", i, R[i]);
}
int bye()
{
char c;
printf("Press [Enter] to exit...\n");
scanf("%c",&c);
return 0;
}
void RUN(int x,int y){Input(x); Run(); Output(y);}
//file MNR.h
#ifndef MNR_H_INCLUDED
#define MNR_H_INCLUDED
#include <stdio.h>
#define START int main(){
#define END return bye();}
//registers count:
const int N = 20;
//commands count:
const int M = 30;
enum command_type {tZ, tS, tT, tJ};
typedef struct
{
command_type type;
int a, b, c;
} TCommand;
void S(int);
void Z(int);
void T(int,int);
void J(int, int, int);
void Input(int arg_c);
void Run();
void Output(int arg_c);
int bye();
void RUN(int,int);
#endif // MNR_H_INCLUDED
Например, если надо написать МНР для функции f(x,y) = x*y, то теперь можно сделать так:
//file main.cpp #include "MNR.h" START J(0,2,9); S(2); J(1,3,7); S(3); S(4); J(0,0,3); Z(3); J(0,0,1); T(0,4); RUN(2,1); END
Теперь для того, чтобы программа для МНР заработала на компьютере, надо подключить модуль MNR.h,
написать строчку START, набрать программу для МНР (теперь команды нумеровать не надо, но надо ставить после каждой » ; «), написать строчку RUN(arg_c_input, arg_c_output) (здесь arg_c_input – это размерность вектора на входе, arg_c_output – на выходе) и потом еще написать строчку END.
Во время выполнения, будет предложено ввести входной вектор, а в конце – будет выведен вектор-результат.
