• ,

Гарвард CS50: задания четвертой недели (лекции 9 и 10)

Подготовка к работе


Как всегда, сначала откройте окно терминала и выполните команду

update50

чтобы убедиться, что ваше приложение уже обновлено.

Прежде, чем приступить к работе, выполните

cd ~ / workspace

wget http://cdn.cs50.net/2015/fall/psets/4/pset4/pset4.zip

чтобы загрузить ZIP-архив этой задачи. Теперь, если вы выполните ls, то увидите, что у вас появился файл с именем pset4.zip в директории ~ / workspace. Извлеките его с помощью команды:

unzip pset4.zip

Если вы еще раз выполните команду ls, то увидите, что появился ещё один каталог. Теперь можно удалить ZIP-файл, как показано ниже:

rm -f pset4.zip

Давайте откроем директорию pset4

cd pset4

выполните ls, и убедитесь, что директория содержит

bmp / jpg / questions.txt


whodunit или «Кто это сделал?»


Если вы когда-нибудь видели рабочий стол Windows XP (https://en.wikipedia.org/wiki/Bliss_(image)) по умолчанию (холмы и голубое небо), то вы видели BMP. На веб-страницах, вы, вероятнее всего, видели GIF. Просматривали цифровые фотографии? Значит, имели радость видеть JPEG. Если вы когда-нибудь делали скриншот на Mac, вы, скорее всего, видели PNG. Прочитайте в интернете о форматах BMP, GIF, JPEG, PNG и ответьте на эти вопросы:

0. Какое количество цветов поддерживает каждый формат?
1. Какой из форматов поддерживает анимацию?
2. Какая разница между сжатием с потерями и без потерь?
3. Какой из этих форматов использует сжатие с потерями?

Те, кто владеют английским, советуем обратиться к статье от МИТ http://cdn.cs50.net/2014/fall/psets/4/garfinkel.pdf.

Если её изучить (или найти в интернете другие ресурсы о хранении файлов на дисках и файловых системах), можно ответить на следующие вопросы:
4. Что происходит с технической точки зрения, когда файл будет удален в файловой системе FAT?
5. Что можно сделать, чтобы обеспечить (с высокой вероятностью) невозможность восстановления удаленных файлов?

А теперь — к нашей истории, плавно перетекающей в первое задание четвертой недели.
Добро пожаловать в Tudor Mansion! Хозяин поместья, мистер Джон Бодди, скоропостижно ушёл от нас, пав жертвой неясной игры. Чтобы выяснить, что произошло, вы должны определить whodunit.

К сожалению, для вас (хотя еще большему сожалению для господина Бодди), единственное доказательство, которое у вас есть — 24-битный BMP файл clue.bmp. Именно его содержимое вы видите ниже. Мистер Бодди успел сделать и сохранить на своем компьютере в свои последние минуты. В файле есть скрытое среди красного «шума» изображения whodunit («ктоэтосделал»). Теперь необходимо поработать над решением как настоящий технический специалист.



Но, для начала, некоторая информация.
Вероятно, проще всего представить изображение в виде сетки пикселей (в смысле, точек), каждая из которых может быть определенного цвета. Чтобы задать цвет точки черно-белого изображения нам нужен 1 бит. 0 может представлять черный, а 1 — белый цвет, как показано на картинке ниже.



Таким образом, изображения, представленные таким образом, — это просто карта битов (bitmap или битмап, так говорят по-английски или на сленге). С черно-белыми всё максимально просто, а для получения цветных изображений нам просто понадобится больше битов на пиксель. Формат файла (например, GIF), который поддерживает «8-битный цвет» использует 8 битов на пиксель. Формат файла (например, BMP, JPG, PNG) с поддержкой «24-битного цвета» использует 24 бита на пиксель (BMP фактически поддерживает 1-, 4-, 8-, 16-, 24- и 32-битную передачу цвета).

В 24-битном BMP, который использует мистер Бодди, для обозначения количества красного цвета уходит 8 бит, столько же — на зеленый, и снова 8 бит для обозначения количества синего в каждом пикселе. Если вы когда-нибудь слышали о цветах RGB, то это оно и есть (R = red = красный, G = green = зеленый, B = blue = синий).

Если значение R, G, и B некоторого пикселя в BMP, скажем, 0xff, 0x00 и 0x00 в шестнадцатеричной системе счисления, то пиксель будет чисто красным, поскольку 0xff (иначе известное как 255 в десятичной системе) означает «много красного» в тот время как 0x00 и 0x00 означают «зеленого нет» и «синего тоже по нулям» соответственно. учитывая насколько красным нам кажется BMP-изображение мистера Бодди, интуитивно ясно, что в «отсеке» для красных значение явно больше, чем в «отсеках» красного с синим. Однако не все пиксели красные, некоторые явно другого цвета.
К слову, в HTML и CSS (языка разметки и помогающих ему таблиц стилей, с помощью которых создают веб-страницы) модели цветов устроены таким же образом. Если интересно, изучите ссылку: https://ru.wikipedia.org/wiki/%D0%A6%D0%B2%D0%B5%D1%82%D0%B0_HTML для получения более подробной информации.

Теперь давайте подойдем к проблеме более технически. Вспомним о том, что файл — это просто последовательность битов, расположенных в некотором порядке. 24-битный BMP-файл — последовательность битов, каждые 24 из которых (ну, почти) определяют цвет какого пикселя. Помимо данных о цвете, BMP-файл также содержит метаданные — информацию о ширине и высоте изображения. Эти метаданные хранятся в начале файла в виде двух структур данных, обычно называемых «заголовками» (не путать с заглавными файлами языка C).

Первым из этих заголовков является BITMAPFILEHEADER, его длина составляет 14 байтов (или 14*8 бит). Второй заголовок — BITMAPINFOHEADER (длиной 40 байтов). После этих заголовков идет следует карта битов: массив байтов, тройки из которых представляют цвет пикселя (1, 4 и 16-бит в BMP, но не 24-или 32, у них есть дополнительный заголовок сразу после BITMAPINFOHEADER. Он называется RGBQUAD, массив, определяющий «значение интенсивности» для каждого из цветов в палитре). Однако BMP сохраняет эти тройки в обратном направлении (можем, сказать, как BGR), с 8 битами на синий, 8 битами на зеленый и 8 битами на красный цвета. К слову, некоторые ВМР также сохраняют весь битовый массив в обратном направлении, начиная с верхней строки изображения в конце файла BMP.

В нашей задаче мы сохранили ВМР так, как описано здесь, сначала верхнюю строку изображения, затем нижние. Другими словами, мы превратили однобитный смайлик в 24-битный, заменяя черное красным. 24-битный BMP будет хранить этот битовый массив, где 0000ff обозначает красный, а ffffff — белый; мы выделили красным цветом все экземпляры 0000ff.

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

Напомним, цифра в 16-ричной системе счисления представляет 4 бита. Соответственно, ffffff в шестнадцатеричном варианте фактически означает 111111111111111111111111 в двоичной системе.

Ну а теперь притормозите, и не идите дальше до тех пор, пока не будете уверены, что понимаете, почему 0000ff обозначает красный пиксель в 24-битном BMP файле.

В окне CS50 IDE раскройте (например, нажатием на маленький треугольник) папку pset4, а в ней — bmp.
В этой папке вы найдете smiley.bmp, кликните по файлу дважды, и вы обнаружите там маленький смайлик размером 8х8 пикселей. В выпадающем меню измените масштаб изображения, скажем со 100% до 400%, это позволит вам увидеть увеличенную, но при этом более «замыленную» версию смайлика. Хотя на деле это самое изображение не должно быть замыленным даже при увеличении. Просто CS50 IDE пытается сослужить вам службу (в стиле сериала ЦРУ) тем, что сглаживает картинку (визуально размывая края). Вот как будет выглядеть наш смайлик, если его увеличить без сглаживания:



Пиксели превратились в большие квадраты.

Продолжим. В терминале переходим в ~/workspace/pset4/bmp. Думаем, вы уже запомнили, как это делать. Давайте изучим выделенные байты в smiley.bmp. Это можно сделать с помощью шестнадцатеричного редактора командной строки, программы xxd. Чтобы его запустить, выполните команду:
xxd -c 24 -g 3 -s 54 smiley.bmp

Вы должны увидеть то, что приведено ниже; мы снова выделены красным цветом все экземпляры 0000ff.


На изображении в крайнем левом столбце вы видите адреса в файле, которые эквивалентны смещению от первого байта файла. Все они приведены в шестнадцатеричной системе счисления. Если перевести шестнадцатеричное 00000036 в десятичную систему, получим 54. Таким образом, вы смотрите на 54й байт из smiley.bmp. Напомним, в 24-битных BMP-файлах первые 14 + 40 = 54 байта заполняются метаданными. Так что, если вы хотите увидеть метаданные, выполните следующую команду:

xxd -c 24 -g 3 smiley.bmp

Если smiley.bmp содержит ASCII-символы, мы их увидим в крайнем правом столбце в xxd вместо всех этих точек.
Итак, smiley — 24-битный BMP (каждый из пикселей представлен с помощью 24 ÷ 8 = 3 байт) размером (разрешением) 8х8 пикселей. Каждая строка (или как её называют «Scanline»), таким образом, занимает (8 пикселей)×(3 байта на пиксель) = 24 байта. Это число кратно четырём, и это важно, поскольку файл ВМР хранится немного по-другому, если число байтов в строке не кратно четырём. Так, в small.bmp, еще одном 24-битном BMP-файле в нашей папке, вы можете видеть зеленое поле размером 3х3 пикселя. Если вы откроете его в программе просмотра изображений, вы увидите, что она напоминает картинку, показанную ниже, только поменьше размером.


Каждая строка в small.bmp, таким образом, занимает (3 пикселя)×(3 байта на пиксель) = 9 байт, что не кратно 4. Чтобы получить длину строки, кратную 4, её забивают дополнительными нулями: между 0 и 3 байтами заполняем каждую строки в 24-битном формате BMP (догадались, почему так?). Для small.bmp, необходимо 3 байта нулей, так как (3 пикселя)×(3 байта на пиксель) + (3 байта заполнения) = 12 байт, которые действительно кратны 4.

Чтобы «увидеть» это заполнение, выполните следующее.

xxd -c 12 -g 3 -s 54 small.bmp


Обратите внимание, мы используем другое значение для -c, чем в случае со smiley.bmp, так что xxd выводит только 4 колонки на этот раз (3 для зеленого квадрата и 1 для заполнения). Для наглядности мы выделили зеленым цветом все экземпляры 00ff00.



Для контраста воспользуемся xxd для файла large.bmp. Он выглядит точно так же, как small.bmp, только его разрешение — 12х12 пикселей, то есть в четыре раза больше. Выполните команду ниже. Возможно, вам понадобится расширить окно, чтобы избежать переноса.

xxd -c 36 -g 3 -s 54 large.bmp


Вы увидите что-то в этом роде:


Обратите внимание, в этом BMP нет отступлений! Ведь (12 точек)×(3 байта на пиксель) = 36 байт, и это кратно 4.

16-ричный редактор xxd продемонстрировал нам байты в наших BMP-файлах. Как нам их получить программным способом? В copy.c есть одна программка, чья единственная цель в жизни — создавать копию BMP, кусок за куском. Да, для этого можно использовать cp. Однако cp не сможет помочь мистеру Бодди. Будем надеяться, что copy.c это сделает, так что выполняем:

./copy smiley.bmp copy.bmp

Если вы теперь выполните ls (с соответствующим флажком), вы увидите, что smiley.bmp и copy.bmp действительно одинакового размера. Давайте еще раз проверим, на самом ли деле это так?
diff smiley.bmp copy.bmp

Если эта команда ничего не вывела на экран, это значит, что файлы действительно идентичны (важно: некоторые программы, тот же Photoshop, включают в себя хвостовые нули на концах некоторых ВМP. Наша версия copy отбрасывает их, так что не беспокойтесь, если в случае копирования других BMP, которые вы скачали или создали для проверки, копия будет на несколько байт меньше, чем оригинал). Вы можете открыть оба файла в программе Ristretto для просмотра изображений (с помощью двойного щелчка), чтобы подтвердить это визуально. Только вот diff делает это сравнение побайтово, поэтому её зрение острее вашего!

Каким образом была создана эта копия? Оказывается, что copy.c связан с bmp.h. Убедимся: открываем bmp.h. Там вы увидите фактические определения этих заголовков, которые мы уже упоминали, адаптированные из собственных реализаций Microsoft. Кроме того, этот файл определяет типы данных BYTE, DWORD, LONG, и WORD, то есть те типы данных, которые, как правило, встречаются в мире Win32 (то есть Windows) программирования. Обратите внимание, они по сути являются псевдонимами для примитивов, с которыми вы (надеемся) уже знакомы. Оказывается, BITMAPFILEHEADER и BITMAPINFOHEADER использовали эти типы. Этот файл также определяет структуру struct, которая называется RGBTRIPLE. Она «инкапсулирует» три байта: один синий, один зеленый и один красный (именно в таком порядке мы будем искать RGB-тройки на диске).

Чем полезны эти структуры struct? Напомним, файл представляет собой просто последовательность байтов (или, в конечном итоге, битов) на диске. Однако эти байты, как правило, упорядочены так, что первые из них представляют собой нечто, затем следующие несколько представляют что-то еще, и так далее. «Форматы» файлов существуют потому, что у нас есть стандарты, или правила, по которым определяется, какие байты что означают. Теперь, мы можем просто прочитать файл с диска в оперативной памяти как один большой массив байтов. И мы помним, что байт в позиции [i] представляет собой одну вещь, в то время как байт в точке [j] является чем-то другим. Но почему бы не дать некоторым этих байтов имена, так что мы могли бы легче извлекать их из памяти? Это именно то, в чем нам помогают структуры в bmp.h. Вместо того, чтобы думать о файле, как об одной длинной последовательности байтов, мы видим его разбитым на более понятные блоки — последовательности структур.

Напомним, smiley.bmp с разрешением 8х8 пикселей, поэтому занимает 14 + 40 + (8 × 8) × 3 = 246 байт на диске (проверить это можно с помощью команды ls). Вот как это выглядит на диске в соответствии с Microsoft:


Видим, что порядок имеет значение, когда дело доходит до членов структур struct. Байт 57 является rgbtBlue (а не, скажем, rgbtRed), потому что rgbtBlue определен в RGBTRIPLE первым. К слову, использование нами атрибута packed гарантирует, что clang не попытается «выравнивать по слову» члены (при этом адрес первого байта каждого члена кратен 4), чтобы мы не получили в наших структурах дыры, которые вовсе не существуют на диске.

Двигаемся дальше. Найдите URL, которые соответствуют BITMAPFILEHEADER и BITMAPINFOHEADER, согласно комментариям в bmp.h. Внимание, торжественный момент: вы начинаете использовать MSDN (Microsoft Developer Network)!

Вместо того, чтобы дальше скроллить copy.c, лучше ответьте на несколько вопросов, чтобы разобраться, как в нем работает код. Как всегда, команда man — ваш верный друг, а теперь еще и MSDN. Если вы не знаете ответов на вопросы, погуглите и поразмышляйте. Вы также можете обратиться к файлу stdio.h в reference.cs50.net/.

Также вы можете запустить copy в debug50 и проделать следующее:
0. Установите точку останова (брейкпойнт) в main (кликнув слева от линейки с номерами строк main)
1. В терминале tab, перейдите по ссылке ~/workspace/pset4/bmp, и откомпиллируйте copy.c в программу copy с помощью make.
2. Выполните debug50 copy smiley.bmp copy.bmp, это откроет панель дебаггера справа.
3. Пройдитесь пошагово по программе, используя панель справа. Обратите внимание на bf и bi. В ~/workspace/pset4/questions.txt, ответьте на вопросы:

• Что такое stdint.h?
• Какова суть использования uint8_t, uint32_t, int32_t и uint16_t в программе?
• Сколько байтов содержит BYTE, DWORD, LONG, и WORD соответственно (Предполагая 32-битную архитектуру)?
• Чем (в ASCII, в десятичной или шестнадцатеричной системе счисления) должны быть первые два байта BMP файла? (ведущие байты, которые используются для идентификации формата файла (с высокой вероятностью) часто называют «магическими числами»).
• Какая разница между bfSize и biSize?
• Что означает отрицательное значение biHeight?
• Какое поле в BITMAPINFOHEADER определяет глубину цвета в BMP (то есть бит на пиксель)?
• Почему функция fopen может вернуть NULL в copy.c 37?
• Почему третий аргумент в fread в нашем коде равен 1?
• Какое значение в copy.c 70 определяет padding, если bi.biWidth равно 3?
• Какие действия выполняет fseek?
• Что такое SEEK_CUR?

Возвращаемся к мистеру Бодди. Задание:

Напишите программу под названием whodunit в файле с именем whodunit.c, которая показывает рисунок мистера Бодди.

Хмммм, что?
Как и copy, программа должна принять ровно два аргумента командной строки, и если вы выполните вашу программу как показано ниже, то результат сохранится в verdict.bmp, в котором рисунок мистера Бодди не будет зашумлен.

./whodunit clue.bmp verdict.b

Позвольте нам предположить, что вы начнете решать эту тайну, выполнив команду ниже.

cp copy.c whodunit.c

Вы можете быть поражены тем, как много строк кода нужно вам написать, чтобы помочь мистеру Бодди.
В smiley.bmp ничего лишнего не скрыто, так что не стесняйтесь проверить программу на этом файле. Он небольшой, и вы можете сравнить вывод вашей программы и вывод xxd в процессе разработки (а, может, всё-таки в smiley.bmp что-то спрятано? На самом деле нет).

Кстати, решить эту задачку можно по-разному. Как только вы идентифицируете рисунок мистера Бодди, он упокоится в мире.

Поскольку whodunit может быть реализован несколькими способами, вы не сможете проверить правильность реализаций с check50. И пусть это вам испортит удовольствие, но решение ассистентов также недоступно для задачи whodunit.
Наконец, в файле In ~/workspace/pset4/questions.txt, ответьте на следующий вопрос:
18. Whodunit? //ктоэтосделал?

resize

Ну а теперь — следующее испытание! Давайте напишем в файле resize.c программу, называемую resize. Она будет менять размеры несжатого 24-битного изображения BMP с шагом в n. Ваше приложение должно принимать ровно три аргумента командной строки, причем первый (n) должен быть целым числом не более 100, второй — именем файла, который будет изменен, а третий — названием сохраненной версии измененного файла.
Usage: ./resize n infile outfile

С помощью такой программы мы могли бы создать large.bmp из файла small.bmp путем изменения размера последнего на 4 (т.е. путем умножения и ширины, и высоты на 4), как показано ниже.
./resize 4 small.bmp large.bmp

Для простоты можно начать задание скопировав еще раз copy.c и назвав копию resize.c.
Но сначала задайте себе вопросы и ответьте на них:
что значит изменить размер BMP (можно предположить, что n помноженное на размер файла infile не будет превышать 232 — 1).
Определите, какие поля в BITMAPFILEHEADER и BITMAPINFOHEADER вам нужно изменить.
Подумайте, нужно ли вам добавить или удалить поля scanlines.
И, да, скажите спасибо, что мы не предлагаем вам рассмотреть все возможные значения n от 0 до 1! (хотя, если интересно — это задачка из хакерского задачника;)). Тем не менее, мы предполагаем, что при n = 1 программа будет работать правильно, и выходной файл outfile будет таких же размеров как и исходный infile.
Хотите проверить программку с помощью check50? Наберите следующую команду:
check50 2015.fall.pset4.resize bmp.h resize.c
Есть желание поиграться с реализацией приложения, выполненной ассистентами CS50? Выполните следующее:
~cs50/pset4/resize

Ну а если хотите посмотреть, например, заголовки large.bmp (в более дружественном для пользователя виде, чем позволяет xxd), нужно выполнить следующую команду:
~cs50/pset4/peek large.bmp

Еще лучше, если вы захотите сравнить свои заголовки с заголовками файлов ассистентов CS50. Вы можете выполнить команды внутри вашей директории ~/workspace/pset4/bmp (подумайте, что делает каждая команда).
./resize 4 small.bmp student.bmp
~cs50/pset4/resize 4 small.bmp staff.bmp
~cs50/pset4/peek student.bmp staff.bmp

Если вы использовали malloc, не забудьте использовать free, чтобы предотвратить утечку памяти. Попробуйте использовать valgrind чтобы проверить наличие утечек.

Как решать?


• Открыть файл, который нам нужно увеличить, а также создать и открыть новый файл, в котором будет записано увеличенное изображение
• Обновить информацию заголовка для выходного файла. Поскольку наше изображение в формате BMP и мы меняем его размер, нам нужно записать заголовок нового файла с новыми размерами. Что поменяется? Размер файла, а также размер изображения — его ширина и высота.



Если мы заглянем в описание заголовка, то увидите переменную biSizeImage. Она указывает на общий размер изображения в байтах, biWidth — ширина изображения минус выравнивание, biHeight — высота. Эти переменные находятся в структурах BITMAPFILEHEADER и BITMAPINFOHEADER. Вы можете найти их, если откроете файл bmp.h.



В описании структуры BITMAPINFOHEADER есть список переменных. Для записи заголовка выходного файла нужно будет поменять значение высоты и ширины. Но есть также вероятность, что позднее вам понадобятся и оригинальные высота и ширина исходного файла. Поэтому лучше сохранить и то, и другое. Будьте внимательны к названиям переменных, чтобы случайно не записать ошибочные данные в заголовок выходного файла.
• Читаем исходящий файл, строка за строкой, пиксель за пикселем. Для этого мы снова обращаемся к нашей библиотеке файлового ввода/вывода и функции fread. Она принимает указатель на структуру, которая будет содержать прочитанные байты, размер одного элемента, который мы собираемся прочитать, количество таких элементов и указатель на файл, из которого мы будем читать.


• Увеличиваем каждую строку по горизонтали согласно заданному масштабу, записываем результат в выходной файл



Как мы записываем файлы? У нас есть функция fwrite, которой мы передаем показатель на структуру, где находятся данные для записи в файл, размер элемента, их количество и указатель на выходной файл. Для организации цикла можем воспользоваться уже привычным нам циклом for.



• Заполнить пробелы! Если количество пикселей в строке не кратно четырем, мы должны добавить «выравнивание» – нулевые байты. Нам понадобится формула для расчета размера выравнивания. Для записи нулевых байтов в выходной файл вы можете использовать функцию fputc, передав ей символ, который вы хотите записать и указатель на выходной файл.



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



• Увеличить размер по вертикали. Это сложнее, но мы можем использовать пример кода из файла copy.c (copy.c открывает исходящий файл, записывает заголовок в выходной файл, читает изображение из исходного файла по строкам, пиксель за пикселем, и записывает их в файл выхода). Исходя из этого, первым делом можно выполнить такую команду: cp copy.c resize.c
Растянуть изображение по вертикали означает скопировать каждую строку несколько раз. Есть несколько разных способов это сделать. Например, с помощью перезаписи, когда мы сохраняем все пиксели одной строки в памяти и в цикле записываем эту строку в выходной файл столько раз, сколько это нужно. Другой метод – перекопирование: после чтения строки исходящего файла, записи его в выходной файл и выравнивания вернуться функцией fseek назад в начало строки в исходящем файле и повторить все заново несколько раз.



recover


В ожидании задачника четвертой недели я провел последние несколько дней за просмотром фотографий, сохраненных моей цифровой камерой в формате JPEG на карте памяти объемом 1 GB CompactFlash (CF). Только не говорите мне, пожалуйста, что на самом деле я провел последние несколько дней на Facebook вместо этого. К сожалению, мои навыки владения компьютером оставляют желать лучшего, и я, сам того не ведая, случайно удалил все фоточки! К счастью, мире компьютеров, «удален» как правило, не равняется «убит». Мой компьютер настаивает на том, что карта-памяти теперь пуста, но я-то знаю, что он лжёт.
Задание: Напишите в ~/workspace/pset4/jpg/recover.c программу, которая восстановит эти фотографии.

Хммм. Ладно, вот еще кое-какое уточнение. Несмотря на то, JPEG-формат сложнее, чем BMP, JPEG имеет «подписи», шаблоны байтов, которые помогут отличить их от других форматов файлов. Большинство JPEG-файлов начинается со следующих трех байтов:

0xff 0xd8 0xff

От первого байта до третьего, слева направо. Четвертый байт, скорее всего, будет одной из следующих комбинаций: 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,0xe8, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef. Иными словами, первые четыре бита четвертого байта JPEG-файла —1110.
Скорее всего, если вы найдете один из этих шаблонов на диске, на котором хранились фотографии (например, моя карта памяти), это и будет начало JPEG-файла. Конечно, вы можете столкнуться с этим на каком диске чисто случайно, восстановление данных нельзя назвать является точной наукой.

Как решать

1. Открыть файл с содержимым карты памяти
2. Найти начало JPEG-файла. Все файлы на этой карте являются картинками в JPEG-формате.
О маркерах JPEG вы уже знаете:



Важно (и приятно) знать, что каждый JPEG-файл сохраняется в памяти единым блоком, а сами файлы следуют один за другим. Изобразим схематическую карту памяти. Каждый прямоугольник — блок длиной 512 байт. Серые прямоугольники — области, где файлы JPEG отсутствуют, звездочками обозначено начало JPEG-файла. Полагаем, что серых блоков между файлами у нас нет.



Как нам прочитать эти данные, эти 512 байтов, чтобы сравнить их начало с заголовком JPEG? Можно воспользоваться уже знакомой нам функцией fread, которая принимает указатель на структуру данных, куда будут записаны прочитанные байты, а также размер элемента, который прочитывается, количество таких элементов и указатель на файл, из которого мы читаем данные.


Мы хотим прочитать 512 байт и сохранить их в буфере. Им будет служить указатель &data, а указатель inptr будет указывать на открытый файл с содержимым карты памяти. Итак, вернемся к структуре нашего файла, в котором сохранено содержимое карты памяти. Мы собираемся читать блоки по 512 байт и сохранять их в буфер, пока не будем знать, что с этим буфером делать. Сначала буфер пуст. Мы читаем первый блок данных, сравниваем его с маркером JPEG и идем дальше.

3. Как только вы находите начало JPEG, вы создаете новый файл на диске. Это можно сделать с помощью функции sprint, в которую передается шаблон и аргумент.



4. и записываете в него порции по 512 байт, пока не найдете начало следующего JPEG с помощью функции fwrite.


5. их можно записывать, пока входной файл карты памяти не закончится. fread возвращает количество элементов размера size, которые были успешно прочитаны. В идеале size должно совпасть c number. Нам нужно организовать условный оператор, который позволит посчитать, сколько элементов на самом деле было прочитано.

  • ,

Вышла 10-я лекция Гарвардского курса CS50 на русском

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

cs50 10 лекция
В шпионских (или любых других) боевиках, вы, наверное, замечали такую штуку: хакер сидит в темной комнате, весь такой загадочный, подсвеченный монитором своего компьютера и всякими цветными диодами непонятного происхождения. На мониторе — не менее загадочные буковки, обычно зелёные с курсором-нижнее-подчеркивание и малюсенькая карта, на которой где-то в дебрях спрятан интересующий спецслужбы объект. Приходит команда «увеличь этот участок изображения», дабы обнаружить, скажем, номер автомобиля, отражённый в чьем-нибудь глазу… И специалист бесконечно масштабирует картинку, пока отражение не станет ясным и четким…

Вам нравятся такие сцены? Если да, спешим вас огорчить: после 10 лекции Гарвардского курса по основам программирования CS50 вы уже не будете смотреть их прежними глазами, понимая всю их несуразицу и преувеличение. Впрочем, будущему программисту это необходимо сделать. Это как рано или поздно все узнают правду о Санта Клаусе. С другой стороны, если в мире будет все больше и больше грамотных с точки зрения IT людей, Голливуду придется повысить качество подобных сцен, не лепя случайные наборы терминов куда ни попадя.

А всё дело в том, что фотографии состоят из пикселей (или точек), и когда мы увеличиваем фотографию, рано или поздно мы дойдем до одного пикселя и как бы мы дальше ни увеличивали изображение, дополнительной глубины не появится, перед нами — конечное количество битов. «Это цифра, детка!».

После четвертой лекции вы сможете приступить к задачнику CS50 для четвертой недели. Он позволит вам прикоснуться к миру графики и криминальной экспертизы: вы напишете коды для восстановления утраченных изображений и изменения масштаба картинок.

Итого, из лекции вы узнаете:

  • Как кодируется изображение. Слово bitmap станет родным и понятным.
  • Вы узнаете, как понять (с точки зрения компьютера), что перед вами именно JPEG-файл и какую роль в этом играет комбинация битов 244 216 255.
  • Вспомните (или изучите) 16-ричные числа. Запись 0хff станет столь же очевидной, как 255 а десятичной системе.
  • Что такое struct в Си? Собственные типы данных в Си.
  • Сравнение содержимого строк в Си (strcmp) и другие средства работы со строками.
  • Адресная арифметика.
  • char* t = malloc((strlen(s) + 1) * sizeof(char)) — как вам такая строчка кода? После лекции вы будете понимать, что к чему, и сами сможете писать нечто подобное =)
  • Немного синтаксического сахара =)
  • Как писать swap с указателями и зачем

Ну и, чтобы расслабиться, напоследок вы посмотрите пластилиновый мультфильм. Не просто мультфильм, но мультфильм про указатели. А если после этого произведения искусства вы только напряжётесь, DJ к вашим услугам.
  • ,

Дополнительные материалы CS50 (Week 3, лекции 7 и 8): асимптотическая нотация, алгоритмы сортировки и поиска

Лекции Гарвардского курса по основам программирования CS50
Задания CS50, week 3, часть 1
Задания CS50, week 3, часть 2

Асимптотическая нотация


Измерить скорость алгоритма реальным временем — секундами и минутами — непросто. Одна программа может работать медленнее другой не из-за собственной неэффективности, а по причине медлительности операционной системы, несовместимости с оборудованием, занятости памяти компьютера другими процессами…

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

Пусть f(x) и g(x) — функции, определенные в некой окрестности x0, причем g там не обращается в 0.
Тогда f является «O» большим от g при (x -> x0), если существует константа C>0, что для всех x из некоторой окрестности точки x0 имеет место неравенство

|f(x)| <= C |g(x)|

Чуть менее строго:
f является «O» большим от g, если существует константа C>0, что для всех x > x0

f(x) <= C*g(x)

Не бойтесь формального определения! По сути, оно определяет асимптотическое возрастание времени работы программы, когда количество ваших данных на входе растет в сторону бесконечности. Например, вы сравниваете сортировку массива из 1000 элементов и 10 элементов и нужно понять, как возрастёт при этом время работы программы. Или нужно подсчитать длину строки символов путем посимвольного прохода и прибавлением 1 за каждый символ:

c - 1 
a - 2
t - 3

Его асимптотическая скорость = О(n), где n — количество букв в слове. Если считать по такому принципу, время, необходимое для подсчета всей строки, пропорционально количеству символов. Подсчет количества символов в строке из 20 символов занимает вдвое больше времени, нежели при подсчете количества символов в десятисимвольной строке.

Представьте, что в переменной length вы сохранили значение, равное количеству символов в строке. Например, length = 1000. Чтобы получить длину строки, нужен только доступ к этой переменной, на саму строку можно даже не смотреть. И как бы мы ни меняли длину, мы всегда можем обратиться к этой переменной. В таком случае асимптотическая скорость = O(1). От изменения входных данных скорость работы в такой задаче не меняется, поиск завершается за постоянное время. В таком случае программа является асимптотически постоянной.

Недостаток: вы тратите память компьютера на хранение дополнительной переменной и дополнительное время для обновления её значения.

Если вам кажется, что линейное время — это плохо, смеем заверить: бывает гораздо хуже. Например, O(n2). Такая запись означает, что с ростом n рост времени, нужного для перебора элементов (или другого действия) будет расти всё резче.
Но при маленьких n алгоритмы с асимптотической скоростью О(n2) могут работать быстрее, чем алгоритмы с асимптотикой О(n).


Но в какой-то момент квадратичная функция обгонит линейную, от этого не уйти.

Еще одна асимптотическая сложность — логарифмическое время или O(log n). С ростом n эта функция возрастает очень медленно. О(log n) — время работы классического алгоритма бинарного поиска в отсортированном массиве (помните разорванный телефонный справочник на лекции?). Массив делится надвое, затем выбирается та половина, в которой находится элемент и так, каждый раз уменьшая область поиска вдвое, мы ищем элемент.



Что будет, если мы сразу наткнемся на искомое, разделив в первый раз наш массив данных пополам? Для лучшего времени есть термин — Омега-большое или Ω(n).

В случае бинарного поиска = Ω(1) (находит за постоянное время независимо от размера массива).

Линейный поиск работает за время O(n) и Ω(1), если искомый элемент — самый первый.
Еще один символ — тета (Θ(n)). Он используется, когда лучший и худший варианты одинаковы. Это подходит для примера, где мы хранили длину строки в отдельной переменной, поэтому при любой её длине достаточно обратиться к этой переменной. Для этого алгоритма лучший и худший варианты равны соответственно Ω(1) и O(1). Значит, алгоритм работает за время Θ(1).

Линейный поиск


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

Вы наверняка замечали, что упорядоченность сильно влияет на то, как вы ищете. Если у вас все рубашки лежат в шкафу, найти среди них нужную обычно проще, чем среди разбросанных без системы по всей комнате.

Линейный поиск — способ последовательного поиска, один за одним. Когда вы пересматриваете результаты поиска в Google сверху вниз, вы используете линейный поиск.

Пример. пусть у нас есть список чисел:

2 4 0 5 3 7 8 1

И нам нужно найти 0. Мы его видим сразу, но компьютерная программа так не работает. Она начинает с начала списка и видит число 2. Затем проверяет, 2=0? Это не так, поэтому она продолжает работу и переходит ко второму символу. Там её тоже ждет неудача, и только на третьей позиции алгоритм находит нужное число.

Псевдокод линейного поиска:



Функция linearSearch получает на вход два аргумента — ключ key и массив array[].Ключ — искомое значение, в предыдущем примере key = 0. Массив — список чисел, которые мы будем просматривать. Если мы ничего не нашли, функция вернет -1 (позицию, которой в массиве нет). Если же линейный поиск найдет нужный элемент, то функция вернет позицию, на которой находится искомый элемент в массиве.
В линейном поиске хорошо то, что он будет работать для любого массива, независимо от порядка элементов: мы всё равно пройдём по всему массиву. Это же является и его слабостью.

Если вам нужно найти число 198 в массиве из 200 чисел, отсортированных по порядку, цикл for пройдет 198 шагов.



Вы, вероятно, уже догадались, какой способ работает лучше для отсортированного массива?

Бинарный поиск и деревья


Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса.



Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть.



По этому же принципу отбрасываем второй столбец. Продолжая такую стратегию, мы найдем Микки буквально за пару шагов.


Давайте найдем число 144. Делим список пополам, и попадаем на число 13. Оцениваем, больше или меньше искомое число, чем 13.



13 < 144, так что мы можем игнорировать всё, что находится левее 13 и само это число. Теперь наш список поиска выглядит так:



Тут чётное число элементов, поэтому выбираем принцип, по которому выбираем «среднее» (ближе к началу или концу). Допустим, мы избрали стратегию близости к началу. В таком случае, наша «середина» = 55.



55 < 144. Мы снова отбрасываем левую половину списка. К счастью для нас, следующее среднее число и будет 144.



Мы нашли 144 в массиве из 13 элементов с помощью бинарного поиска всего за три шага. Линейный поиск в такой же ситуации справился бы аж за 12 шагов. Поскольку этот алгоритм на каждом шаге уменьшает количество элементов в массиве вдвое, он найдет искомое за асимптотическое время О(log n), где n – количество элементов в списке. То есть, в нашем случае асимптотическое время = O(log 13) (это чуть больше трёх).

Псевдокод функции бинарного поиска:



Функция принимает на вход 4 аргумента: искомое key, массив данных array [], в котором находится искомое, min и max — указатели на максимальное и минимальное число в массиве, на которое мы смотрим на данном шаге алгоритма.

Для нашего примера изначально дана такая картинка:



Разберем код далее. midpoint — наша середина массива. Она зависит от крайних точек и находится по центру между ними. После того, как мы нашли середину, проверяем, меньше ли она нашего числа key.



Если это так, то key также больше, чем любое из чисел левее середины, и мы можем вызвать бинарную функцию снова, только теперь наш min = midpoint + 1. Если окажется, что key < midpoint, мы можем отбросить само это число и все числа, лежащие справа от него. И мы вызываем бинарный поиск по массиву от числа min и вплоть до значения (midpoint – 1).



Наконец, третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы.



Наконец, может статься так, что искомое число и вовсе отсутствует в массиве. Для учёта этого случая делаем такую проверку:



И возвращаем (-1), чтобы указать, что мы ничего не нашли.

Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действия:

  1. Отсортировать список и применить бинарный поиск
  2. Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.

Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:

  • Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов)
  • Каждый узел имеет 0, 1 или 2 потомка
  • Оба поддерева — левое и правое — являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
  • У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.



Внимание: корень «программистского» дерева, в отличие от реального, находится сверху. Каждая ячейка называется вершиной, вершины соединены ребрами. Корень дерева — ячейка с номером 13. Левое поддерево вершины 3 выделено цветом на картинке снизу:



Наше дерево соответствует всем требованиям к бинарным деревьям. Это значит, что каждое его левое поддерево содержит только значения, которые меньше или равны значению вершины, правое — только значения большие или равные значению вершины. Оба левые и правые поддеревья сами являются бинарными поддеревьями.

Способ построения бинарного дерева — не единственный: ниже на картинке вы видите ещё один вариант для того же набора чисел, и их может быть очень много на практике.



Такая структура помогает проводить поиск: минимальное значение находим, двигаясь от вершины влево-вниз каждый раз.



Если нужно найти максимальное число — идем от вершины вниз и вправо. Нахождение числа, которое не является минимальным или максимальным также весьма простое. Мы спускаемся от корня влево или вправо в зависимости от того, больше или меньше наша вершина искомой. Так, если нам нужно найти число 89 мы проходим вот такой путь:



Еще можно выводить числа в порядке сортировки. Например, если нам нужно вывести все числа в порядке возрастания, берем левое поддерево и начиная с самой левой вершины идем наверх.
Прибавить что-то в дерево тоже просто. Главное помнить о структуре. Скажем, нам нужно добавить в дерево значение 7. Идем к корню, и проверяем. Число 7 < 13, поэтому идем влево. Там видим 5, и идем вправо, поскольку 7 > 5. Дальше поскольку 7 > 8 и 8 не имеет потомков, мы конструируем ветку от 8 влево и на неё цепляем 7.





Также можно удалять вершины из дерева, но это несколько сложнее.
Есть три разных сценария для удаления, которые мы должны учесть.

  1. Самый простой вариант: нам нужно удалить вершину, у которой нет потомков. Например, число 7, которое мы только что добавили. В таком случае мы просто проходим путь до вершины с этим числом и удаляем его.
  2. У вершины есть одна вершина-потомок. В таком случае можно удалить нужную вершину, но её потомка нужно подсоединить к «дедушке», то есть вершине, из которой произрастал её непосредственный предок. Например, из того же дерева нужно удалить число 3. В таком случае, её потомка, единицу, вместе со всем поддеревом присоединяем к 5. Это делается просто, поскольку все вершины, слева от 5, будут меньше чем это число (и меньше, чем удалённая тройка).



  3. Самый сложный случай — когда у удаляемой вершины есть два потомка. Теперь первым делом нам нужно найти вершину, в которой спрятано следующее большее значение, нужно поменять их местами, а потом удалить нужную вершину. Обратите внимание: следующая по значению вершина не может иметь двух потомков, тогда её левый потомок будет лучшим кандидатом на следующее значение.

    Давайте из нашего дерева удалим корневую вершину 13. Сначала ищем самое близкое к 13 число, которое его больше. Это 21. Меняем 21 и 13 местами и удаляем 13.






Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка?



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



Это ничуть не лучше, чем линейный поиск. Есть и другие структуры данных, более сложные. Но их мы пока рассматривать не будем. Скажем только, что для решения проблемы с построением дерева из отсортированного списка можно перемешать входные данные случайным образом.

Алгоритмы сортировки



Есть массив чисел. Нужно его отсортировать. Для простоты будем считать, что мы сортируем целые числа в порядке возрастания (от меньшего к большему). Существует несколько известных способов провернуть этот процесс. Плюс, вы всегда можете пофантазировать на тему и придумать модификацию алгоритма.

Сортировка выбором




Основная идея — разбить наш список на две части, отсортированную и неотсортированную. На каждом шаге алгоритма новое число перемещается из неотсортированной части в отсортированную, и так пока все числа не окажутся в отсортированной части.

  1. Находим минимальное неотсортированное значение.
  2. Меняем местами это значение с первым неотсортированным значением, ставя его таким образом в конец отсортированного массива.
  3. Если остались неотсортированные значения, возвращаемся к шагу 1.

На первом шаге все значения являются неотсортированными. Назовем неотсортированную часть — Unsorted, а отсортированную — Sorted (это просто английские слова, и делаем мы это только потому, что Sorted — гораздо короче, чем «Отсортированная часть» и будет лучше смотреться на картинках).



Находим минимальное число в неотсортированной части массива (то есть, на этом шаге — во всем массиве). Это число 2. Теперь меняем его с первым среди неотсортированных и ставим его в конец отсортированного массива(на этом шаге — на первое место). На этом шаге это первое число в массиве, то есть 3.



Шаг второй. На число 2 мы не смотрим, оно уже в отсортированном подмассиве. Начинаем искать минимальное, начиная со второго элемента, это 5. Убеждаемся, что 3 — минимальное среди неотсортированных, 5 — первое среди неотсортированных. Меняем их местами и прибавляем 3 к отсортированному подмассиву.



На третьем шаге мы видим, что в неотсортированном подмассиве самое маленькое число — 4. Меняем его с первым числом среди неотсортированных — 5.



На четвертом шаге мы обнаруживаем, что в неотсортированном массиве минимальное число — 5. Меняем его с 6 и прибавляем к отсортированному подмассиву.



Когда среди неотсортированных остается только одно число (наибольшее), это значит, что весь массив отсортирован!



Вот как выглядит реализация массива в коде. Попробуйте сделать его самостоятельно.



В обоих, самом лучшем и самом худшем случаях, чтобы найти минимальный неотсортированный элемент, мы должны сравнить каждый элемент с каждым элементом неотсортированного массива, и делать это мы будем на каждой итерации. Но нам нужно просматривать не весь список, а только неотсортированную часть. Меняет ли это скорость алгоритма? На первом шаге для массива из 5 элементов мы делаем 4 сравнения, на втором — 3, на третьем — 2. Чтобы получить количество сравнений, нам нужно сложить все эти числа. Мы получаем сумму

формула

Таким образом, ожидаемая скорость алгоритма в лучшем и худшем случае — Θ(n2).

Не самый эффективный алгоритм! Тем не менее, для учебных целей и для небольших массивов данных — вполне применимый.

Пузырьковая сортировка

Алгоритм у пузырьковой сортировки — один из простейших.

Идем вдоль всего массива и сравниваем 2 соседних элемента. Если они в неправильном порядке, меняем их местами. При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания).

Повторять первый шаг, если хотя бы один обмен на предыдущем шаге был совершен.

Давайте отсортируем массив.



Шаг 1: идем по массиву. Алгоритм начинает работу с первых двух элементов, 8 и 6 и проверяет, находятся ли они в правильном порядке. 8 > 6, поэтому меняем их местами. Далее мы смотрим на второй и третий элементы, теперь это 8 и 4. Из тех же соображений меняем их местами. В третий раз сравниваем 8 и 2. Итого, мы делаем три обмена (8, 6), (8, 4), (8, 2). Значение 8 «всплыло» в конец списка на правильную позицию.



Шаг 2: меняем местами (6,4) и (6,2). 6 теперь на предпоследней позиции, и её можно не сравнивать с уже отсортированным «хвостом» списка.



Шаг 3: меняем местами 4 и 2. Четверка «всплывает» на свое законное место.



Шаг 4: проходимся по массиву, но менять нам уже нечего. Это сигнализирует о том, что массив полностью отсортирован.



А это — код алгоритма. Попробуйте реализовать его на Си!



Пузырьковая сортировка проходит за время O(n2) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n2/2 – n/2), но этим можно пренебречь.
В лучшем случае (если все элементы уже стоят на своем месте), мы справимся за n шагов, т.е. Ω(n), поскольку нам нужно будет просто пробежаться по массиву один раз и убедиться, что все элементы стоят на своих местах (т.е. даже n-1 элементов).

Сортировка вставками


Основная идея этого алгоритма — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части.



Давайте на примере ниже разберем, как работает сортировка вставкой. До того, как мы начали, все элементы считаются неотсортированными.



Шаг 1. Возьмем первое неотсортированное значение (3) и вставим его в отсортированный подмассив. На этом шаге весь отсортированный подмассив, его начало и конец и будут этой самой тройкой.



Шаг 2. Поскольку 3 > 5, мы вставим 5 в отсортированный подмассив справа от 3.



Шаг 3. Теперь работаем над вставкой числа 2 в наш отсортированный массив. Сравниваем 2 со значениями справа налево, чтобы найти правильную позицию. Поскольку 2 < 5 и 2 < 3 и мы дошли до начала отсортированного подмассива. Следовательно, мы должны вставить 2 слева от 3. Для этого подвигаем 3 и 5 вправо, чтобы появилось место для двойки и вставляем её в начало массива.



Шаг 4. Нам повезло: 6 > 5, поэтому мы можем вставить это число сразу за числом 5.


Шаг 5. 4 < 6 и 4 < 5, но 4 > 3. Следовательно, мы знаем, что 4 нужно вставить справа от 3.
Снова, мы вынуждены подвинуть 5 и 6 вправо, чтобы создать лакуну для 4.


Готово!

Обобщенный алгоритм:

Берем каждый неотсортированный элемент n и сравниваем его со значениями в отсортированном подмассиве справа налево, пока не определим подходящую позицию для n (то есть, в тот момент, когда находим первое число, которое меньше, чем n). Затем сдвигаем все отсортированные элементы, которые находятся справа от этого числа вправо, чтобы образовалось место для нашего n, м вставляем его туда, тем самым расширяя отсортированную часть массива.
Для каждого неотсортированного элемента n нужно:
  1. Определить место в отсортированной части массива, куда нужно вставить n
  2. Сдвинуть отсортированные элементы вправо, чтобы сделать лакуну для n
  3. Вставить n в образовавшуюся лакуну в отсортированной части массива.

А вот и код! Рекомендуем написать свою версию программы сортировки.



Асимптотическая скорость алгоритма

В самом плохом случае мы сделаем одно сравнение со вторым элементом, два сравнения с третьим и так далее. Таким образом наша скорость равна O(n2).
В лучшем случае мы будем работать с уже отсортированным массивом. Отсортированная часть, которую мы строим слева направо без вставок и передвижений элементов займет время Ω(n).

Сортировка слиянием

Этот алгоритм — рекурсивный, он разбивает одну большую задачу сортировки на подзадачи, выполнение которых делают его ближе к решению изначальной большой задачи.
Основная идея — разделение неотсортированного массива на две части и сортировка отдельных половинок по рекурсивному принципу.



Допустим, у нас есть n элементов для сортировки. Если n < 2, заканчиваем сортировку, иначе — сортируем отдельно левую и правую части массива, и потом их объединяем.
Давайте отсортируем массив


Делим его на две части, и продолжаем делить, пока не получим подмассивы величиной 1, которые заведомо отсортированы.



Два отсортированных подмассива можно объединить за время O(n) с помощью простого алгоритма: удаляем меньшее из чисел в начале каждого подмассива и вставляем его в объединенный массив. Повторяем, пока не закончатся все элементы.





Сортировка слиянием требует времени O(nlog n) для всех случаев. Пока мы делим массивы на половины на каждом уровне рекурсии получаем log n. Затем, для слияния подмассивов нужно всего n сравнений. Следовательно, O(nlog n). Лучший и худший варианты для сортировки слиянием — одинаковы, ожидаемое время работы алгоритма = Θ(nlog n).

Этот алгоритм — самый эффективный среди рассмотренных.



  • ,

Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 2

Лекции Гарвардского курса по основам программирования CS50
Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска
Задания третьей недели, часть 1. Сортировка и поиск.

Игра начинается!





Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали (если, конечно, есть куда двигаться). Цель — расположить числа по порядку, от 1 до 15 слева направо сверху вниз. Тогда пустое место окажется в правом нижнем углу.

Движение любой плитки (или нескольких) является «шагом» в этом игровом пространстве. Представленная на картинке выше комбинация уже сложена, но обратите внимание, что плитка 12 или 15 могут быть сдвинуты в пустое пространство. Правила гласят, что плитка не может перемещаться по диагонали или извлекаться из игральной доски.

На самом деле конфигураций для начала игры — много (можете посчитать, сколько именно), но давайте для простоты расположим плитки в порядке от наибольшей к наименьшей и оставим пустое пространство в правом нижнем углу доски. Единственное, давайте поменяем местами 1 и 2, чтобы головоломка была разрешимой.



Теперь перейдите в директорию ~/ рабочей среды, затем — в /pset3/fifteen и откройте файл fifteen.c.

В нем — код «движка» игры. Задание состоит в том, чтобы дописать код игры.

Но для начала давайте откомпиллируем наш «движок» (вы наверняка уже знаете, как это сделать). Невзирая на то, что игра не закончена, запустить приложение можно.

Будет удобнее запустить его в большем, чем обычно, окне терминала, которое можно открыть, нажав на зеленый плюс (+) рядом с одной из вкладок кода и выбрав New Terminal. Или же можно открыть терминальное окно на полный экран, кликнув на иконку Maximize в правом верхнем углу консоли.

Вы видите, что кое-что кое-как работает. Но на самом деле большая часть игры ещё не написана. И вот тут — приготовьтесь — ваш выход!

Исследование

Изучите код и комментарии fifteen.c, после чего ответьте на вопросы ниже:

  1. Помимо доски 4х4, какую размерность поля допускает наш движок?
  2. Какой структурой данных является игровое поле?
  3. Какая функция вызывается для приветствия игрока в начале игры?
  4. Какие функции вам необходимо реализовать?
  5. Примечание: если вы хотите, чтобы автопроверка ответила вам, правильно ли вы ответили на вопросы, рядом с файлом fifteen.c найдите файл fifteen.txt и запишите в него ответы на эти вопросы.

Реализация

Что ж, начнем реализовывать игру. Помните, двигаемся крохотными шажками, не пытайтесь сделать всё и сразу. Вместо этого давайте реализовывать функции по очереди и убедитесь, что они работают прежде, чем двигаться вперед. В частности, мы предлагаем вам реализовать функции игры в следующем порядке: init (инициализация), draw (прорисовка), move (сделать шаг), won (выигрыш). Дизайнерские решения (например, сколько пробелов нужно вставлять между нашими плитками-числами) — остаются за вами. Игровое поле должно выглядеть примерно так:

15 14 13 12

11 10  9  8

7  6  5  4

3  1  2  _

Еще раз обращаем внимание, что в стартовой позиции 1 и 2 расположены в обратном порядке (это касается классического поля 4х4 если количество плиток — нечетное). Если количество плиток чётное, а поле — 3х3, менять две «младших» плитки местами не нужно.

8  7  6

5  4  3

2  1  _


Чтобы протестировать вашу реализацию «Пятнашек», нужно попробовать поиграть в них (не забывайте, аварийный выход из программы до её естественного завершения можно вызвать комбинацией клавиш crtl+c). Убедитесь, что программа будет работать, если будут введены неправильные числа. И помните, что точно так же, как вы автоматизировали ввод в find, вы можете автоматизировать «прохождение» игры.
На деле, в папке ~cs50/pset3 есть файлы 3x3.txt и 4x4.txt, где собраны все последовательности шагов для победы на полях размерности 3х3 и 4х4. Чтобы протестировать программу, например, с помощью первого из файлов, выполните следующую команду:

./fifteen 3 < ~cs50/pset3/3x3.txt

Настройте нужный вам аргумент для ускорения анимации. Да и вообще, при желании вы всегда можете изменить игру. Чтобы поразвлекаться с «управляющими последовательностями ANSI», включая цвет. Обратите внимание на нашу реализацию clear и проверьте http://isthe.com/chongo/tech/comp/ansi_escapes.html чтобы усвоить новые трюки.

При желании напишите свои собственные функции или поменяйте прототипы функций, которые писали мы. Единственное ограничение — не меняйте логику функции main, иначе мы не сможем применить к ней некоторые автоматические тесты для подтверждения корректности работы вашей программы. В частности, main должна возвращать 0, в том и только том случае, если пользователь сложил головоломку. Не нулевые значения нужно вернуть для всех вариантов ошибок.
Если возникают какие-то ошибки, пишите нам. Ну а если захотите поиграть с реализацией приложения, подготовленного ассистентами CS50, выполните следующую команду:

~cs50/pset3/fifteen

Если вам интересно увидеть более крутую реализацию, с автоматическим решением головоломки, посмотрите «Хакерскую» версию программы:

~cs50/hacker3/fifteen

Вместо того, чтобы ввести номер в окошке игры, напечатайте слово GOD. Здорово, не так ли?
Если хотите проверить правильность вашей программы официально с check50, обратите внимание, что check50 предполагает, что пустое пространство игрового поля заполнено 0; если вы выбрали другое значение, для корректной проверки замените его на нуль. Кроме того, check50 предполагает, что вы индексируете поля игрового поля в порядке [ряд] [столбец], а не доска [столбец] [строка].

check50 2015.fall.pset3.fifteen fifteen.c


Подробнее о реализации функций игры Fifteen

  • init (инициализация)
  • draw (прорисовка)
  • move (сделать шаг)
  • won (выигрыш)

init

В этой функции мы представляем игровое поле. Для этого используем двумерный массив целых чисел. Размерность массива — MAX x MAX, где MAX — константа, обозначающая максимальное количество плиток, которые могут поместится в строке или столбце поля.

Таким образом нам нужно определить переменную int board[MAX][MAX]

Однако вспомним, что размерность игрового поля определяет пользователь. Поэтому нужно определить переменную, которая бы обозначала размерность доски, которую должен ввести пользователь. Это int d.

где d — размерность доски, d <= MAX. Однако в Cи вы не можете менять размер массива, поэтому придется довольствоваться максимальной размерностью. В init вам нужно поместить значения на доску.


Почитайте больше о двумерных массивах, если вы с ними ещё не работали. Вкратце, у них два индекса, первый обозначает номер строки, второй — номер столбца. Для нашей задачи мы начинаем с максимального числа и заканчиваем в случае d = 3 («Восьмяшки») единицей и пустым углом. Если у нас все-таки «Пятнашки», тогда 1 и 2 меняем местами. Что же делать с пустым местом? Наш массив состоит из целых чисел, поэтому и пустота должна быть заполнена неким целым. Поэтому вы должны выбрать некое целое число для инициализации пустой плитки (а в случае физической игры, её отсутствие).

Чтобы инициализировать игровое поле и заполнить его стартовым набором плиток, можно использовать циклы.
Ведем циклы по индексам i и j, где board[i][j] — плитка, которая находится в строке номер i и столбце номер j. Заполняем доску в убывающем порядке. В случае, если количество плиток (без пустой) — нечетное, меняем местами 1 и 2.

draw
Эта функция должна напечатать текущее состояние игрового поля. Помним, что у нас могут быть значения с одним или двумя разрядами, поэтому для красивого форматирования после чисел 1-9 функция должна печатать пробел (#s). Это можно организовать с помощью плейсхолдера %2d.

printf (“%2d”, board[i][j]);

Также не забывайте о пустой клетке. Выберите символ, который будет её представлять (в нашем примере — это нижнее подчеркивание). Функция draw должна отрисовывать этот символ, как только вы попадаете на пустую клетку. Итак, наш цикл будет примерно таким:

for каждой строки 
for каждого элемента строки 
print значение и пробел 
print новую строку

Запомните, что порядок, в котором функция draw выводит на экран плитки, должен отображать порядок, в котором они находятся в массиве, определенном в функции init.
move
Как только вы инициализировали игровое поле и нарисовали начальные позиции плиток, нужно позволить пользователю редактировать положение плиток, то есть, совершать движения.

Итак, в Fifteen.c программа принимает вывод от пользователя, строит игровое поле и затем вызывает функцию move, и говорит, какую плитку он хочет подвинуть. Будьте внимательны: вы применяете функцию именно к номеру на плитке, а не к её положению на доске (в массиве). Таким образом, вам нужно найти актуальное положение плитки. Кроме того, вы должны позволить пользователю подвинуть плитку только тогда, когда это возможно.



На картинке выше мы можем подвинуть только плитки номер 2, 5 и 8. Как это определить? По значению пустой плитки. Таким образом, функция move работает примерно так:

  • Принимает номер плитки, который пользователь хочет подвинуть
  • Ищет положение в массиве (на игровом поле) этой плитки
  • Запоминает позицию пустой плитки
  • Если пустая плитка соседствует с той, которую пользователь хочет подвинуть, они меняются местами в массиве.

won
Эта функция проверяет, завершилась ли игра после каждого шага пользователя. Она возвращает true, если плитки стоят в правильном порядке (в том числе и положение пустой плитки в правом нижнем углу). В таком случае программу можно завершить. Если же плитки всё еще разбросаны, функция возвращает false и передает бразды правления функции move.

Как организовать проверку? Как и в случае инициализации и рисования доски — с помощью двух вложенных циклов for. Например, можно поставить условие, что каждое последующее число в массиве должно быть больше предыдущего. Обратите внимание на то, какое значение записано в пустой плитке. Или другой способ — используйте счетчик, чтобы убедиться, что все плитки на местах, если справитесь и напишете формулу, чтобы это получить. Желаем удачи в экспериментах!

Как подтвердить правильность кода и получить оценки


Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.

  1. Залогиньтесь в CS50 IDE
  2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашей директории pset3 и нажмите Download. Вы должны увидеть, что браузер загрузил архив pset3.tar.gz.
  3. В отдельном окне или вкладке залогиньтесь в CS50 Submit
  4. Кликните по иконке Submit в левом верхнем углу экрана
  5. В списке папок слева кликните по директории Problem Set 3, затем нажмите на кнопку Upload New Submission. Она находится справа.
  6. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.
  7. Перейдите к той папке, где вы сохранили pset3.tar.gz. Скорее всего, он находится в папке Downloads(«Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете pset3.tar.gz, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
  8. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
  9. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.
  • ,

Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 1

Лекции Гарвардского курса по основам программирования CS50
Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска
Часть вторая. «Пятнашки» на Си

Подготовка


Прежде, чем браться за задачи, посмотрите лекции 7-8, прочитайте и вникните в «Дополнительные материалы третьей недели». Они посвящены алгоритмам поиска (линейному и бинарному), сортировки (много их!), а также работе дебаггера (умение работать с дебаггером для отладки программ — чрезвычайно важный навык!).

Если с лекциями и теорией все пошло, как надо, вы без труда ответите на проверочные вопросы:

  • Почему бинарный поиск требует отсортированного массива?
  • Почему оценка сортировки пузырьком равна O (n2)?
  • Почему оценка сортировки вставками — это Ω (n)?
  • Как работает сортировка выбором? Опишите в трех предложениях (или меньше).
  • Каков верхний предел (наихудший случай) времени работы сортировки слиянием?
  • Дебаггер GDB позволяет отладить программу. А если сформулировать конкретнее, что именно он позволяет делать?

Цели


  • Научиться работать с проектами, которые содержат несколько файлов
  • Научиться читать чужой исходный код
  • Усвоить различные алгоритмы и рекурсивные функции

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

Начинаем

Напомним, для решения практических задач на первой и второй неделе, вы писали программы с нуля и создали собственные каталоги pset1 и pset2 с помощью команды mkdir. Для практического задания третьей недели, нужно загрузить дистрибутив (или «дистро», мы так его называем), написанный нами, и добавить туда собственные строки кода. Сначала вчитайтесь в наш код и постарайтесь его понять. Важнейший навык этой недели — научиться читать чужой код.

Итак, залогиньтесь на cs50.io и выполните команду

update50

в терминальном окне, чтобы убедиться в актуальности версии рабочего пространства. Если вы случайно закрыли терминальное окно и не можете его найти, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так). Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.



После этого выполните команду

cd ~/workspace

и убедитесь, что вы находитесь внутри директории workspace (это ваш каталог). После этого выполните команду:

wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip

чтобы загрузить ZIP-архив задачника в ваше рабочее пространство (wget — команда linux для загрузки). Если всё ок, в строке вы увидите такую фразу:

'pset3.zip' saved

Убедитесь, что вы действительно скачали pset3.zip выполнив команду:

ls

а затем запустите

unzip pset3.zip

чтобы разархивировать файл. Если теперь вы еще раз запустите команду ls, вы также увидите директорию pset3. Перейдите в неё, выполнив команду

cd pset3

а затем снова запросите просмотр содержимого директории:

ls

вы увидите, что в этой директории есть две поддиректории:

fifteen  find

Уже интригует!

Поиск

Давайте теперь нырнем в одну из этих поддиректорий. Для этого выполним команду:

cd ~/workspace/pset3/find

Если вы выведете содержимое этой папки на экран (вы уже, наверное, помните, как это делать), вот что вы должны увидеть:

helpers.c  helpers.h  Makefile  find.c  generate.c

Ух ты, файлов хватает. Но не беспокойтесь, сейчас мы с ними разберёмся.
В файле generate.c размещён код программы, которая использует «генератор псевдослучайных чисел» (генерация посредством функции drand48) чтобы сгенерировать большое количество случайных (по правде говоря, псевдослучайных, компьютеры не могут работать с чистой случайностью!) чисел, и разместить их по одному в строке. Скомпилируйте программу:

make generate

Теперь запустите её, выполнив команду:

./generate

Программа выдаст вам следующее сообщение:

Usage: generate n [s]

Это значит, что программа ожидает один или два аргумента командной строки. Использование первого, n, обязательно; это число означает, сколько псевдослучайных чисел вы хотите создать. Параметр s не является обязательным, на что указывают квадратные скобки. Число s можно назвать «семенами» для генератора псевдослучайных чисел. Под «семенами» подразумеваем входные данные в генератор псевдослучайных чисел, которые влияют на его вывод.

Например, если вы используете drand48, сначала вызвав srand48 (еще одна функция, цель которой заключается в „посеве“ drand48) с аргументом, скажем, 1, а затем вызовете drand48 три раза, drand48 может вернуть 2728, потом 29785, потом 54710.

Tсли вы вместо предыдущего, используя drand48, сначала вызовете srand48 с аргументом, скажем, 2, а затем снова используете drand48 три раза, drand48 может вернуть 59797, потом 10425, потом 37569. Но если вы повторно «посеете» drand48, вызывая srand48 снова с аргументом 1, в результате следующих трех вызовов drand48 вы снова получите 2728, потом 29785, потом 54710!

Видите, все происходит совсем не случайно.
Запустите программу еще раз, на этот раз, скажем, n = 10, как показано ниже; вы увидите список из 10 псевдослучайных чисел.

./generate 10

Давайте запустим программу в третий раз с тем же значением n; вы должны увидеть другой список из 10 цифр. Теперь попробуйте запустить программу с двумя параметрами. Давайте возьмем s = 0, как показано ниже.

./generate 10 0

Теперь запустите ту же команду еще раз:

./generate 10 0

Можно даже не спорить: вы снова увидели ту же самую «случайную» последовательность из десяти цифр. Вот что произойдет, если вы не будете менять «семена» генератора псевдослучайных чисел.

Теперь посмотрим на саму программу generate.c (помните, как?).
Комментарии в начале этого файла объясняют общую функциональность программы. А вот сам код мы, похоже, забыли прокомментировать. Внимательно вчитайтесь в код, и читайте его до тех пор, пока не уловите смысл каждой строки. После этого прокомментируйте этот код вместо нас, заменяя каждый TODO фразой, описывающей цель или функциональность соответствующей строки или строк кода. (примечание: unsigned int — это «беззнаковый» int, то есть он не может быть отрицательным). Чтобы получить более подробную информацию о rand или srand, выполните:

man drand48

или

man srand48

После того, как в generate.c откомментируете всё, что можно, перекомпилируйте программу, чтобы убедиться, что вы ничего не сломали:

make generate

Если generate больше не компилится, чините, что сломали:)!

Напомним: команда make автоматизирует компиляцию кода, поэтому вам не придется выполнять команду clang вручную подставляя кучу переключателей. Но на самом деле make просто упрощает нам ввод, а на деле за ним спрятан тот же clang с нужными нам параметрами. Однако когда ваши программы станут больше по размеру, make не сможет больше выяснить из контекста, как компилировать код. В таком случае вам придется указать make, как нужно скомпилировать программы, особенно если они связаны с использованием различных исходных файлов (например, .c). Для решения этой проблемы мы будем использовать файлы конфигурации (Makefiles), которые точно указывают make, что нужно делать.

Как команда make узнала, как нам следует компилировать generate? На самом деле команда использовала конфигурационный файл, который мы уже написали. Этот файл называется Makefile и он лежит в той же директории, что и generate.c. Makefile — некий список правил, указывающих, как создать файл generate из generate.c. В файле вы найдете, в частности соответствующие строки:

generate: generate.c
    clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c

Первая строка говорит make, что „цель“ под названием generate должна быть создана путем вызова команды из второй строки. Более того, первая строка указывает make, что generate зависит от generate.c, смысл которого в том, что make будет только пересобирать generate в ходе последующих запусков, если этот файл был изменен. Неплохой трюк для экономии времени, не так ли? На самом деле, выполните команду ниже снова, если вы не меняли generate.c.

make generate

Вам сообщат, что generate уже обновлен до текущей версии.

Замечание: отступление в начале второй строки не является последовательностью пробелов, это, скорее, знак табуляции. К сожалению, make требует, чтобы командам предшествовали знаки табуляции, так что будьте осторожны, чтобы не изменить их на пробелы, иначе вы столкнетесь с непонятными ошибками! Флаг -Werror говорит команде clang считать предупреждения (плохо) ошибками (еще хуже), так что вы будете вынуждены (в хорошем, обучающем смысле!) исправить их.

Теперь посмотрим на файл find.c. Обратите внимание, эта программа ожидает один аргумент командной строки: „иглу“, которую нужно найти в «стоге сена» значений. После этого, просмотрите код и скомпилируйте программу, выполнив команду ниже.

make find

make практически вывел для нас следующее:

clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Обратите внимание! Только что вы скомпиллировали приложение, состоящее е из одного, а из двух файлов: helpers.c и find.c. Каким образом об этом узнала make? Чтобы понять это, снова откройте файл Makefile, чтобы понять, что там на самом деле творится. Соответствующие строки ниже.

find: find.c helpers.c helpers.h
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Под зависимостью (после двоеточия) можно понимать то, что все изменения в файлы find.c, helpers.c, или helpers.h вынудят make пересобирать find следующий раз, когда она будет вызвана для этих целей.
Теперь запустите эту программу, выполнив, например, следующее:

./find 13

После этого вам поступит предложение предоставить некий стог (то есть целые числа), и подавать их по одной соломинке за раз. Как только вы устанете от ввода чисел, нажмите комбинацию клавиш Ctrl-D. Эта комбинация пошлет программе символ конца файла (EOF, end-of-file). Символ вынудит функцию GetInt из библиотеки CS50 вернуть константу INT_MAX, а она, в свою очередь в find.c заставит find прекратить набирать «стог».
Теперь программа будет искать иглу в том стоге сена, что вы предоставили, и в конечном счете она сообщит, была ли она найдена. Говоря кратко, программа выполняет поиск некоторого значения в массиве. По крайней мере, она должна, но загвоздка в том, что пока что она ничего не найдет! Но тут на помощь приходите вы! О важности вашей роли поговорим чуть позднее.

На самом деле процесс предоставления стога можно автоматизировать хотя бы по „слиянию“ вывода generate в find в качестве входных данных. Например, команда ниже передает 1000 псевдослучайных чисел в find, которая затем ищет среди этих значений 42.

./generate 1000 | ./find 42

Обратите внимание: когда generate передает исходные данные в find, вы не видите числа generate, но вы увидите работу find.

В качестве альтернативы, вы можете „перенаправить“ вывод generate в файл с помощью такой команды:

./generate 1000 > numbers.txt

Содержимое этого файла можно перенаправить на вход find с помощью команды:

./find 42 < numbers.txt

Давайте еще разок посмотрим на код в Makefile и обратим внимание на следующую строку:

all: find generate

Это означает, что вы можете собрать generate и find, выполнив следующую команду:

make all

Более того, команда под этой строкой эквивалентна команде над ней, поскольку make строит первую запись в Makefile по умолчанию.

make

Если бы вы только могли свести все эти практические задания к одной команде! Но — увы!
Наконец, обратите внимание на эти последние строки в Makefile:

clean:
    rm -f *.o a.out core find generate

Эта запись позволяет вам удалить все файлы, которые заканчиваются на .o или называются core (это мы поясним чуть позднее!), а также запустить программы find или generate просто выполнив строку:

make clean

Если захотите экспериментировать, то вот с чем будьте осторожны: не добавляйте, скажем, *.c в эту последнюю строку Makefile! (почему?) Все строки, которые начинаются со знака # — это просто комментарии.

Задание 1: Search


Пришло время для кое-чего интересного! Обратите внимание, find.c вызывает search, функцию, объявленную в helpers.h. К сожалению, мы забыли реализовать эту функцию полностью в helpers.c! (Надо отметить, что мы могли бы поместить содержимое helpers.h и helpers.c в один find.c. Но иногда лучше разделять программы на несколько файлов. Особенно если некоторые функции, точнее функции-утилиты, могут оказаться полезными и для других программ. Как, например, функции из библиотеки CS50.

Взгляните на helpers.c и вы увидите, что search всегда возвращает значение false, независимо от того, занесено ли данное значение value в values. Перепишите search таким образом, чтобы она использовала линейный поиск, возвращая true, если value входит в values и false, если value не входит в values. Позаботьтесь о том, чтобы вернуть false сразу, если n не является положительным.
Когда вы будете готовы к проверке правильности, попробуйте вызвать следующую команду:

./generate 1000 50 | ./find 127

Поскольку одно из чисел, выведенных с помощью generate, когда «засеивали» 50, равно 127, ваш код должен найти „иголку“! Для контраста попробуйте выполнить и такую команду:

./generate 1000 50 | ./find 128

Поскольку 128 не входит во множество чисел, выведенных функцией generate, когда «засеивали» 50, ваш код не должен найти «иглу». Проведите и другие тесты, запуская generate с каким-то семенем, анализируя выходные данные, и ища «иголку», которая должна быть в «стогу».

Обратите внимание, что main в find.c написана таким образом, что find возвращает 0, если «игла» найдена, иначе — возвращает 1. Вы можете проверить так называемый „выходной код“, который main возвращает при выполнении

echo $?

После запуска некоторых других команд. Например, если ваша реализация search — правильна, если вы запустите

./generate 1000 50 | ./find 127
echo $?

Вы увидите 0, пока 127 есть среди тех 1000 чисел, выведенных с помощью generate с семенем 50, поэтому написанный вами поиск search должен возвратить true. В этом случае main (написанный нами) должен вернуть 0 (то есть завершить работу). Если же вы зададите следующие входные данные

./generate 1000 50 | ./find 128
echo $?

Вы увидите 1, поскольку 128 не находится среди тех 1000 чисел, которые были выведены с помощью generate с семенем 50. В этом случае search (написанный вами) вернет false, и main (написанный нами) вернет 1 (и с тем закончит работу). Сечёте логику?

Когда всё будет готово для проверки с помощью check50, выполните такую команду:

check50 2015.fall.pset3.find helpers.c

Кстати, не стоит привыкать тестировать код с помощью check50 перед собственным тестированием. Всё-таки check50 не в реальности не существует, поэтому запуск кода с вашими собственными входными выборками, сравнение фактического вывода к ожидаемым выходных данных, — лучшая привычка, которую можно обрести на этом этапе. Правда-правда, не приобретайте вредную зависимость!

Если вам интересно поиграть с реализацией find, выполненной ассистентами cs50, выполните такую команду:

~cs50/pset3/find

Сортировка


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

Обратите внимание: find.c вызывает sort, функцию, объявленную в helpers.h. К сожалению, мы «забыли» реализовать эту функцию в полной мере в helpers.c! Загляните в helpers.c, и вы увидите, что происходит мгновенное возвращение sort, хотя функция main из find действительно передает ей фактический массив.
Теперь вспомните синтаксис объявления массива. Вы не только указываете тип элементов этого массива, но также задаете его размер в квадратных скобках. Так мы делаем для haystack в find.c:

int haystack [MAX];

Но при прохождении массива вы только указываете его имя. И мы это делаем точно так же, когда проходим haystack, чтобы выполнить sort в find.c:

sort (haystack, size);

(Догадайтесь, почему мы передаем размер этого массива отдельно?)
Когда мы объявляем функцию, которая принимает в качестве аргумента одномерный массив, не нужно указывать размер массива. Точно так же мы этого не делали, когда объявляли sort в helpers.h (и helpers.c):

void sort (int values [] int n);

Реализуйте sort, так чтобы функция действительно отсортировывала массив чисел от меньших к большим. Нужно, чтобы время ее работы было равно O (n2), где n — размер массива. Скорее всего, вы захотите реализовать метод пузырьковой сортировки, сортировка выбором, или вставкой, поскольку мы изучили их на третьей неделе. Тем не менее, важно отметить: „правильного“ способа реализации не существует для этих алгоритмов. Есть огромное количество вариаций. На самом деле, вы всегда можете улучшить их, если считаете нужным, до тех пор, пока ваша реализация сойдется к O (n2). Тем не менее, эксперименты оставьте для тела функции, а с целью упрощения проверки, не меняйте нашу декларацию sort. Она должна выглядеть так:

void sort (int values [] int n);

Поскольку функция возвращает значение типа void, она не должна возвращать отсортированный массив. Вместо этого, она должна „деструктивно“ сортировать фактический массив, по которому она «пробегает», перемещая его элементы. На четвертой неделе мы будем обсуждать, что массивы передаются не по значению, а по ссылке. То есть, sort не получит копии массива, а сам исходный массив.

Хотя вы не можете изменить нашу декларацию sort, вы всегда можете определить свою собственную функцию в helpers.c, которые затем можно будет вызвать из sort.

Выберите сами, как лучше протестировать реализацию вашей sort. Не стоит забывать, что printf и GDB вам помогут! И не забывайте, что вы можете создать ту же последовательность псевдослучайных чисел снова и снова, явно указывая значения семян для generate.

Бинарный поиск, советы


Первое, что необходимо понимать о функции find — у нас уже есть написанный код (дистрибутив). Мы просто заполняем некие пробелы в уже существующем коде.

Программа find.c запрашивает ввод чисел (то есть, заполнить «стог»), а потом ищет в нем «иголку» по запросу пользователя, используя для этого sort и search — функции, определенные в helpers.c. Таким образом, find уже написана, нам нужно написать helpers.

Итак, вот что нам нужно сделать:

  1. Реализовать search. Эта функция должна возвращать true, если значение найдено в «стогу» и false, если его там нет.
  2. Реализовать sort, функцию, сортирующую массив значений.

Изначально поиск реализован как линейный. Но вы можете сделать лучше. Алгоритм линейного поиска выполняется за время О(n). Ваша задача — написать алгоритм бинарного поиска. Время его исполнения — O(log n). Однако его проблема в том, что ему на вход нужно подавать отсортированные данные, иначе он не будет работать. Вы помните пример с разорванной книгой, и, вероятно, знаете, почему так.

Если вы прошлись бинарным поиском по элементам и их больше не осталось (то есть в этом «стоге» нашей «иголки» попросту нет), нужно, чтобы функция вернула false.

Бинарный поиск можно реализовать итеративно или рекурсивно (о рекурсии Дэвид Малан рассказал в восьмой лекции).
  • ,

Вышла восьмая лекция гарвардского курса CS50 на русском

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

cs50 на русском 8 лекций

Восьмая лекция Гарвардского курса по основам программирования CS50 пройдет в необычной обстановке: Дэвид Малан окажется в окружении зелёных стен библиотеки Вайднера. И пускай они выглядят не так эффектно, как полюбившийся студентам театр Сандерса (та самая огромная торжественная аудитория, в которой обычно проходят занятия), это никак не повлияло на увлекательность лекции! В этот раз мы:

  • Узнаем, может ли рекурсия помочь нам в поисках Майка Смита. И вообще, узнаем, что это за загадочный инструмент такой — рекурсия — и как её применять.
  • Разберемся, с понятием сортировки слиянием, и поймем, как можно её реализовать с помощью рекурсии. Снова разделяем и властвуем, уже практически по привычке.
  • Станем на шаг ближе к пониманию загадочного компилятора Clang и его работе. Продолжим разбираться с тем, что находится «под капотом» программы и оценим путь от исходного кода через ассемблерный к объектному.
  • Столкнемся с такими вот знаками: & | ^ ~. Это— не «птичий язык», а побитовые операторы, они позволяют добраться до отдельных битов данных. Для расшифровки каждого из них Дэвид воспользуется весьма необычным инструментом — доской и маркерами! Даже такое «ретро» изредка проскакивает на CS50 =).
  • А еще Дэвид приоткроет завесу тайны: в практическом задании вам предстоит вспомнить детство и поиграть в «пятнашки». Только в этот раз они будут написаны на Си.
  • Наконец, вы увидите милую беседу Эрика Шмидта из Google и одного бывшего сенатора с каким-то знакомым лицом по имени Барак. Эрик попросил Барака предложить самый эффективный способ отсортировать миллион 32-битных целых чисел. Ответ нынешнего президента США вы узнаете из лекции.
  • ,

Вышла седьмая лекция гарвардского курса CS50 на русском

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

7 лекция cs50 на русском

Помните разорванный телефонный справочник из самой первой лекции CS50? В седьмой лекции он возвращается! Возвращается, чтобы сделать фразу «эффективность алгоритмов» не пустым звуком, а пояснить на примере. Все программисты думают о скорости работы программы и о том, сколько памяти она при этом «съест». На учебных задачках это не так очевидно, но когда мы работаем с большими массивами данных (как почти везде в «Энтерпрайзе»), эти вопросы становятся первоочередными.

Представьте себе, что данные в телефонном справочнике не отсортированы по алфавиту. Представляете, сколько времени у нас бы ушло на то, чтобы его там найти? С учётом того, что в телефонном справочнике нет человека с таким именем, пришлось бы перебирать все строчки подряд — и всё впустую! Но есть выход: данные всегда можно отсортировать.

И в седьмой лекции Дэвид Малан расскажет об известных алгоритмах сортировки — пузырьковой, вставки и выбора. Эффективны ли они? Подсказка: не слишком, в чем это проявляется — узнаете из лекции. Но почему они в таком случае знамениты и зачем их изучать? Дело в том, что они довольно просты в реализации, а на их основе можно создавать уже более продвинутые алгоритмы сортировки.

А еще, вы услышите, как звучат алгоритмы сортировки. Незабываемая музыка программирования уже доступна в переводе седьмой лекции.
  • ,

Вышла седьмая лекция гарвардского курса CS50 на русском

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

Помните разорванный телефонный справочник из самой первой лекции гарвардского курса CS50? В седьмой лекции он возвращается! Возвращается, чтобы сделать фразу «эффективность алгоритмов» не пустым звуком, а пояснить на примере. Все программисты думают о скорости работы программы и о том, сколько памяти она при этом «съест». На учебных задачках это не так очевидно, но когда мы работаем с большими массивами данных (как почти везде в «Энтерпрайзе»), эти вопросы становятся первоочередными.

Представьте себе, что данные в телефонном справочнике не отсортированы по алфавиту. Представляете, сколько времени у нас бы ушло на то, чтобы его там найти? С учётом того, что в телефонном справочнике нет человека с таким именем, пришлось бы перебирать все строчки подряд — и всё впустую! Но есть выход: данные всегда можно отсортировать.

И в седьмой лекции Дэвид Малан расскажет об известных алгоритмах сортировки — пузырьковой, вставки и выбора. Эффективны ли они? Подсказка: не слишком, в чем это проявляется — узнаете из лекции. Но почему они в таком случае знамениты и зачем их изучать? Дело в том, что они довольно просты в реализации, а на их основе можно создавать уже более продвинутые алгоритмы сортировки.

А еще, вы услышите, как звучат алгоритмы сортировки. Незабываемая музыка программирования уже доступна в переводе седьмой лекции.

Вышла шестая лекция гарвардского курса CS50 на русском

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

Каждый раз, когда вы ловите себя на том, что копируете и вставляете куски кода, спрашивайте себя: а нет ли другого способа? В шестой лекции Гарвардского курса по основам программирования CS50 будет много полезного для нахождения «других способов», но и веселья хватит сполна.

cs50 6 лекция

Кстати, её будет вести молодой лектор Роб Боуден. Но Дэвид Малан также вертикально поприсутствует=). Что значит «вертикально»? Узнаете в начале лекции.

Ну а потом начнется серьезная работа:

• Роб объяснит, что такое массивы, одномерные и многомерные;
• что такое аргументы командной строки, какова их связь с элементами массивов и как их использовать непосредственно в программах;
• Немного приоткроет завесу тайны над тем, что такое криптография (но подробнее о шифрах узнаете из дополнительных материалов).

Смотрите лекцию, читайте о шифрах, и… не забывайте решать побольше задач!
  • ,

Гарвард CS50: задания второй недели (лекции 5 и 6)

cs50 задания к лекциям 5 и 6

Лекции CS50 лежат здесь: http://javarush.ru/cs50.html. В этом материале — 3 задания, теоретические сведения к ним и руководство к действию.

Цели


• Углубиться в функции и библиотеки
• Познакомиться с криптографией, реализовать пару простых шифров

Дополнительные материалы


reference.cs50.net/ — разъяснение функций библиотек, используемых во время обучения. На английском.
http://computer.howstuffworks.com/c.htm стр. 11 – 14 и 39

Подготовка


Залогиньтесь на cs50.io, выполните

update50

чтобы убедиться в актуальности версии вашего рабочего пространства. Если вы случайно закрыли терминальное окно, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так).


Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.


Создайте рабочую директорию:

mkdir ~/workspace/pset2

Обратите внимание: между mkdir и ~/workspace/pset2 есть пробел. Напомним, ~ означает корневой каталог, ~/workspace — папка, называемая рабочим пространством, находится внутри корневого каталога, ~/workspace/pset2 — директория по имени pset2 внутри ~/workspace.
Теперь выполните:

cd ~/workspace/pset2

чтобы перейти в новую директорию.

Командная строка выглядит примерно так:

username:~/workspace/pset2 $

Если что-то не так, повторите шаги. Также можете вызвать команду

history

чтобы просмотреть последние несколько команд в хронологическом порядке. Также вы можете, установив курсор на командную строку и нажимая стрелку «вверх» на клавиатуре, просматривать все команды в порядке от последней введенной к первой. С помощью кнопки «вниз» вы можете идти обратно. Кстати, вместо того, чтобы каждый раз набирать одни и те же команды, вы можете прокручивать уже набранные команды и выполнять их снова, нажимая на Enter. Вы могли заметить, что Дэвид на лекциях делает именно так.

Задачи второй недели нужно сохранять в pset2.

Задание 0. Инициализация


Ознакомимся со строками поближе. В файле initials.c напишите программу, которая запрашивает имя пользователя (с помощью функции GetString получаем имя в виде строки) и затем выводит первые буквы имени (или имен) и фамилии в верхнем регистре без пробелов, точек и прочих знаков, только с переводом строки (\n). Предполагаем, что пользователи вводят исключительно буквы (в нижнем или верхнем регистре, или обоих сразу) плюс по одному пробелу между словами. Считайте, что ребята с именами Joseph Gordon-Levitt, Conan O’Brien или David J. Malan не будут пользоваться программой.

username:~/workspace/pset2 $ ./initials
<u>Zamyla Chan</u>
ZC
username:~/workspace/pset2 $ ./initials
robert thomas bowden
RTB

Для проверки корректности работы программы вызывайте check50:

check50 2015.fall.pset2.initials initials.c

Хотите поиграться с реализацией программы, подготовленной сотрудниками CS50? Набирайте строку:

~cs50/pset2/initials


Криптография

Криптография, наука о шифровке и дешифровке информации… На самом деле зашифрованные послания существуют с древних времён, и использовались армиями для передачи секретных сообщений. Ну и сейчас ваши пароли в Facebook и других сетях хранятся в зашифрованном виде.

Задание 1. Аве, Цезарь!


Теоретические сведения
Мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв ниже в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ 3, то буква C перейдет в F, а Z — в C.

Примеры: используем шифр Цезаря с ключом 5 на слове cat.

c -> h
a -> f
t -> y 
Caesar (cat, 5) = hfy

Ключ = 7, слово = computer

c->j
o->v
m->t
p->w
u->b
t->a
e->l
r->y
Caesar(computer,7) = jvtwbaly



Шифр Цезаря прост, но, увы, ненадёжен (это взаимосвязанные вещи!): для английского алфавита — всего 25 вариантов шифровки, перебрать все варианты легко даже без компьютера. Тем не менее, шифр Цезаря часто используют в качестве шага в других шифрах, таких, как шифр Виженера (о нём — в следующем пункте).

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле:

ci = (pi + k) % 26

Привыкайте к такой формализации, она позволяет программировать алгоритм и выражает смысл шифра точно и сжато.
Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Or fher gb qevax lbhe Binygvar!


Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале). Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечетко выражаете свои мысли=).

Условие

Написать в файле caesar.c, программу, шифрующую текст с помощью шифра Цезаря. На вход программы подавайте один аргумент командной строки: не негативное целое число. Для простоты назовем его k. Если пользователь выполняет программу без аргументов командной строки или более, чем с одним аргументом, приложение должно возмутиться и вернуть значение 1 (обычно так обозначают ошибки):
return 1;

Во всех других случаях программа запрашивает у пользователя текст, который нужно зашифровать, затем выводит на экран текст, зашифрованный ключом k (т.е., смещенный на k позиций вправо по циклу). Если в тексте есть символы, выходящие за пределы английского алфавита, их программа не меняет. После вывода шифрованного текста, приложение завершает работу,main возвращает 0:

return 0;

Если main не возвращает нуль явно, он возвращается автоматически (на самом деле int — тип, возвращаемый main, но об этом в другой раз). Согласно конвенции (правилам хорошего тона в программировании), если вы явно возвращаете 1 чтобы указать на ошибку, то нужно вернуть и 0 в качестве указателя на успешное завершение работы программы.

Хотя в английском алфавите только 26 букв, k может быть и больше 26. По сути, ключ k = 27 даст тот же результат, что и k = 1, но нужно позволить пользователю вводить любое неотрицательное число, не превышающее 2^31 – 26 (оно должно поместиться в int). Программа также должна учитывать, что строчные буквы шифруются строчными, а прописные — прописными.

С чего начинаем? Поскольку приложение должно принять значение k непосредственно в строке аргументов, заголовок функции main у нас имеет следующий вид:

int main(int argc, string argv[])

Из шестой лекции вы знаете, что argv — это массив строк. Массив можно представить, как ряд шкафчиков-ячеек в спортзале. В каждом из них спрятано некоторое значение. В нашем случае, внутри каждой ячейки лежит аргумент типа

string

Чтобы открыть первый шкафчик, используем argv[0], второй — argv[1] и так далее. Если у нас есть n замков, то нам нужно остановиться на argv[n — 1], поскольку argv[n] уже не существует (или существует, но принадлежит кому-то ещё, нам лучше его не трогать).

Таким образом, вы можете получить доступ к аргументу k следующим образом:

string k = argv[1];

Мы полагаем, что там действительно что-то есть! Напомним, argc — переменная типа int, равная количеству строк argv. Значит, лучше проверить значение argc прежде, чем пытаться открыть ячейку, ведь может статься, что её не существует.

В идеале argc = 2. Почему так? Внутри argv[0] обычно находится имя программы. То есть, argc всегда не меньше 1. Но нашей программе нужно, чтобы пользователь предоставил аргумент командной строки k, следовательно, argc = 2. Естественно, если пользователь в командной строке введет более одного аргумента, argc также подрастает и может быть больше, чем 2.

Если пользователь вводит целое число в строку, это еще не значит, что внесенное значение будет автоматически сохранено в тип int. Точнее, оно НЕ будет. Оно будет string, даже если выглядит точь-в-точь, как int! Так что нам нужно конвертировать string в int самостоятельно. К счастью, существует функция atoi, созданная для этих целей. Её синтаксис:

int k = atoi(argv[1]);

Обратите внимание: k имеет тип int, поэтому с ним можно провернуть арифметические действия. С этой функцией не нужно беспокоиться, введет ли пользователь целое число, или, скажем, foo: в таком случае atoi возвратит 0.

Функция atoi объявлена в библиотеке stdlib.h, поэтому не забудьте прописать её директивой #include в начале программы. Код и без этого скомпиллируется, поскольку мы уже включили эту функцию в библиотеку cs50.h. Тем не менее, лучше доверять нативным библиотекам.

Итак, вы получили k, сохраненное как int. Теперь запросим ввод текста. Если вы делали задания первой недели, то уже знакомы с функцией библиотеки CS50, которая называется GetString. Она-то нам и поможет.

После того, как вы получили k и начальный текст, приступим к шифрованию. Напомним, вы можете пройтись по всем символам строки и напечатать их с помощью следующего цикла:

for (int i = 0, n = strlen(p); i < n; i++)
{
    printf("%c", p[i]);
}

Другими словами, точно так же, как argv — массив строк, string является массивом символов. Поэтому мы можем использовать квадратные скобки для доступа к отдельным элементам строки точно так же, как получать отдельные строки в argv. Конечно, нет ничего криптографического в печати каждого из символов. Или, технически, когда k = 0. Но мы же должны помочь Цезарю зашифровать его текст! Аве, Цезарь!

Чтобы использовать strlen, нужно подключить ещё одну библиотеку.

Поскольку мы автоматизируем некоторые проверочные тесты, программа должна себя вести себя ровно следующим образом:

username:~/workspace/pset2 $ ./caesar 13
Be sure to drink your Ovaltine!
Or fher gb qevax lbhe Binygvar!


Помимо atoi, вы можете найти другие классные функции в библиотеках ctype.h и stdlib.h. Для этого перейдите по ссылке и поройтесь там немного. Например, isdigit — явно что-то интересное=).
Когда переходите от Z к A (или от z к a), не забывайте об операторе деления по модулю % в языке С. Также изучите таблицу, она показывает символы ASCII не только для букв.

Чтобы проверить правильность работы программы с check50, выполните следующее:

check50 2015.fall.pset2.caesar caesar.c

А если вам интересно поиграть с кодом, сделанным сотрудниками СS50, выполните команду:

~cs50/pset2/caesar


Кстати, uggc://jjj.lbhghor.pbz/jngpu?i=bUt5FWLEUN0.

Разбор задания
  1. Получить ключ
  2. Получить текст
  3. Зашифровать
  4. Вывести на экран зашифрованное сообщение

1. Формируем функцию main так, чтобы пользователь вводил ключ в командной строке и проверяем ключ на корректность.

int main(int argc, string argv[])

argc:
• int
• количество аргументов, введенных в командную строку
• если argc = 2 все ок. Если нет, выводим инструкцию и закрываем программу.
• Если argc = 2 проверяем, является ли ключ целочисленным
• Argv — это массив строк, список с введенными в него аргументами

Массив — структура данных, содержащая разные данные одного типа в разных ячейках.


Например, пользователь ввел строку blastoff Team Rocket, тогда:


Переводим с помощью функции atoi() полученное в целое число. Если это невозможно, функция вернет 0.



2. Запрос у пользователя текста. Это просто: всё, что вводит пользователь, является строкой.
3. Шифрование. Алгоритм прост, но как пояснить компьютеру, какие буквы идут одна за другой? Самое время вспомнить о таблице ASCII!


Однако в строке могут быть не только буквы… Прежде, чем перейти к изменению строк, представьте, что нужно поменять только один символ. Мы хотим сменить буквы из начального текста, а не знаки или цифры. Что мы должны сделать? Для начала нам нужно проверить, есть ли этот символ в алфавите. Это можно сделать с помощью функции isalpha().

Если символ входит в алфавит, эта функция возвращает значение true и false во всех других случаях. Еще две полезные функции — isupper () и islower() возвращают true в случае, если буква прописная или строчная соответственно. Таким образом:

Isalpha(‘Z’) -> true
Isalpha(‘;’) -> false
Isupper(‘Z’) ->true
Isupper(‘z’) -> false
Islower(‘Z’) -> false
Islower(‘z’)->true


Если isalpha возвращает true, нам нужно поменять этот символ с помощью ключа.
Рассмотрим и разберем в качестве примера программу Замили, ассистента CS50.

/*
 * asciimath.c
 * by Zamyla Chan
 *
 * Calculates the addition of a char and an integer,
 * and displays both the resultant character and its
 * ASCII value.
 *
 * Usage: ./asciimath key [char]
 *
 */

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, string argv[])
{

    if (argc != 2)
    	
    	{
 printf("print the key next time \n"); 
        return 1;
    	}
    // key is the second command line argument 

  
    int key = atoi(argv[1]); //преобразование строки в int 

    int letter = 'A';
    
    printf("\nCalculating '%c' + %d...\n", letter, key);
    
    int result = (letter + key);
        
    printf("The ASCII value of %c is %d.\n\n", result, result);
   
    return 0;
    

}

Вас может удивить, почему ‘A’ — это целое число, тогда как она явно является буквой. Оказывается символы и целые числа — взаимозаменяемы. Поставив букву A в одиночные кавычки можно получить её ASCII-код в int. Будьте внимательны: вам нужны именно одинарные кавычки, без них компилятор будет искать переменную по имени A, а не символ.

Затем в строке

int result = (letter + key);


мы прибавляем значение ключа к ASCII-коду буквы и сохраняем их в переменной целого типа. Даже если результат имеет тип int, оператор printf использует плейсхолдер %с для символов. Таким образом, программа печатает символ, связанный с целочисленным результатом. Во втором случае мы выводим на экран число с помощью плейсхолдера %d.

Вы можете ввести этот код в сs50 IDE и поиграться с ним. Проверим работу asciimath для разных ключей. Возьмем значение 25, увидим следующую картинку:



А теперь пусть ключ будет 26:



Мы получили [, а вовсе не букву A. Это просто следующий символ ASCII после Z. Так что простое прибавление ключа работать не будет. Нам нужно использовать формулу шифра, чтобы возвращаться в начало алфавита как только буквы закончатся.
Помните, мы уже писали выше:

ci = (pi + k) % 26

Где ci — буква номер i в шифрованном тексте, pi — буква номер i в незашифрованном тексте, k — ключ, а %26 — остаток от деления на 26 (или «деление по модулю 26»).

Давайте применим эту формулу для буквы Y. Возьмем k = 2. Посчитаем (‘Y’ + 2) %26
ASCII-код буквы ‘Y’= 89. Тогда
(‘Y’ + 2) %26 = (89 + 2)%26 = 91%26 = 13

Но это вовсе не ASCII-значение нужной нам буквы A, которое равно 65.

Теперь давайте придадим каждой букве алфавита значение от 0 до 25 по порядку. В таком случае Y = 24.
(24+2)%26 = 0
Буква А как раз имеет такой индекс. Таким образом, эта формула относится к алфавитному индексу букв, а не их ASCII-значений.

Для печати зашифрованного символа вам нужно будет его ASCII-значение. И разберитесь с тем, как переключаться между ASCII-значением и номером в алфавите.
После того, как мы выяснили формулу для одного символа, нужно применить её для каждой буквы во вводимой с клавиатуры строке. Но только если это буквы!
И помните, для больших и малых букв нужны разные значения. Тут пригодятся функции isupper и islower. У вас может быть две формулы, одна для больших букв, другая — для малых, функции помогут выбрать, какую из них применить.

Как применить формулу к каждому отдельному символу в строке? Помним, что строка — это просто массив символов. Определить количество итераций в цикле поможет функция strlen (длина строки).


Задание 2. Parlez-vous français?

Теория

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

Пример:

p = Meet me in the park at eleven am 
В качестве ключевого слова возьмем 
k = bacon
Длина сообщения p = 25 
В то время как длина k = 5 
Поэтому его нужно повторять 5 раз.



Если число букв в сообщении не делится на ключ нацело, мы в последнем применении ключа используем только его часть:


Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа bacon в алфавите (от a до z). Считаем с нуля, как истинные программисты. И каждую букву в оригинальном тексте смещаем на заданное число, как в шифре Цезаря, возвращаясь при надобности после Z в начало алфавита. Таким образом, M сместится на 1, первая e вообще не сместится, а вторая сместится на 2 позиции. Ниже вы видите изначальное сообщение, расписанный ключ и результат его применения.


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


Также можно использовать полный перебор, но вариантов немало: 26^n – 1 где n — длина неизвестного ключа. Но обычно это немало. Правда, для компьютера это не проблема.
А теперь математика шифра:

Пусть р – некоторый текст, k — ключевое слово, kj — j-я буква ключа, pi — буква под номером i в оригинальном тексте, ci — буква под номером i в шифровке. Тогда:

ci = (pi + kj) % 26

Задание
Условие

Написать программу vigenere.c, которая шифрует сообщение с помощью шифра Виженера. На вход программы подаем один аргумент командной строки: ключевое слово k, состоящее из букв английского алфавита. Если приложение запускается более чем с одним аргументом или с аргументом не входящим в алфавит, нужно вывести информацию об ошибке с завершением программы. То есть main будет возвращать 1 — в таком случае наши автоматические тесты поймут, что здесь все хорошо, и это условие учтено. Если всё хорошо, программа должна перейти к запросу строки текста p, который мы и шифруем полученным выше ключом k, напечатать результат и завершить выполнение программы, возвратив значение 0.
Уточнение

Нужно сделать так, чтобы в ключе k символы A и a обозначались как 0, B и b как 1, ..., Z и z как 25. Программа должна применять шифр Виженера только к буквам текста p. Остальные символы (цифры, знаки препинания, пробелы) нужно вывести без изменений. Если алгоритм собирается применить j-й символ k к i-му символу p, не входящему в алфавит, применяем этот j-й символ ключа к следующему алфавитному символу в тексте; вы не можете просто оставить его и перейти к другому символу в k. Наконец, программа должна сохранить регистр каждой буквы в p.

Не знаете, с чего начать?




Вот вам несколько советов от Замили, ассистента курса CS50

К счастью, программа очень похожа на шифр Цезаря, только в качестве ключа используется не целое число, а строка. Если вы успешно реализовали шифр имени римского правителя, он может стать прекрасным стартом для реализации второго задания. Вы, вероятно, уже смекнули, что шифр Виженера с одной буквой в качестве ключа — это тот же шифр Цезаря.
В алгоритме Виженера применяются те же шаги, что и в «Цезаре»:
  1. Получить ключ
    • кодовое слово — это второй аргумент командной строки argv[1]
    • должен входить в алфавит: функция isalpha

  2. Получить текст
  3. Зашифровать
  4. Напечатать шифрованный текст
Итак, второй аргумент командной строки argv[1] проверим на принадлежность к алфавитным символам. Делаем это с помощью уже знакомой isalpha. Если ключ корректен, получаем от пользователя строку и начинаем шифровать.

Формула шифра Виженера похожа на формулу шифра Цезаря. Каким образом вы преобразуете букву на соответствующее смещение шифра? Попробуйте сравнить значения по таблице ASCII.


Скорее всего, у вас получится отыскать закономерность между буквами и их алфавитными индексами используя последовательности в таблице. Догадались, как отнять одну букву от другой, чтобы получить желаемый результат? Смещения для больших и малых букв одинаковы, так что вам придется определить две похожие формулы для определения смещения для строчных и отдельно для прописных букв.
Также не забудьте, что цикл прохода по тексту должен игнорировать символы, не входящие в английский алфавит. И не забудьте сохранить регистр букв.
Если посмотреть на формулу шифра:

ci = (pi + kj) % 26

вы увидите две индексные переменные, i и j. Одна сохраняет позицию в исходном тексте, другая — в ключе. Если ваш текст длиннее ключа, индекс по ключу проходит с конца ключа снова в его начало.
Как это сделать? С помощью операции деления по модулю! Результат операции — остаток от деления двух чисел. Практическая польза этой операции в программировании просто огромна!

Представьте, что многочисленную группу людей нужно разделить на три подгруппы. Один из способов это сделать — попросить их рассчитаться на первый-второй-третий.


То есть, первый человек относится к первой группе, второй — ко второй, третий — к третьей, четвертый — снова к первой и так далее. Вы можете использовать деление по модулю чтобы произвести эту же операцию. Пронумеруем те же три группы с нуля. Вот как это делается:



Если вы возьмете индекс и поделите его по модулю максимального значения, полученный результат никогда не будет больше или равен этому значению.

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

Так как мы автоматизируем некоторые тесты вашего кода, программа должна вести себя так, как показано ниже:

jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon
Meet me at the park at eleven am
Negh zf av huf pcfx bt gzrwep oz


Как еще можно протестировать программу, кроме ручного вычисления зашифрованного текста? Мы добрые: для этого мы написали программу devigenere. Она принимает один и только один аргумент командной строки (ключевое слово), а её работа заключается в том, чтобы принять зашифрованный текст в качестве входных данных и вернуть обычный.
Запустите её:

~cs50/pset2/devigenere k

Где k — ключевое слово.
Если вы хотите проверить правильность вашей программы с помощью check50, выполните:

check50 2014.fall.pset2.vigenere vigenere.c


А если хотите оценить нашу реализацию vigenere, наберите:

~cs50/pset2/vigenere


Как подтвердить правильность кода и получить оценки


Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.
  1. Залогиньтесь в CS50 IDE
  2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашему файлу initials.c, находящемуся в директории pset2 и нажмите Download. Вы должны увидеть, что браузер загрузил initials.c.
  3. Повторите для caesar.c.
  4. Повторите для vigenere.c.
  5. В отдельном окне или вкладке залогиньтесь в CS50 Submit
  6. Кликните по иконке Submit в левом верхнем углу экрана.



  7. В списке папок слева кликните по директории Problem Set 2, затем нажмите на кнопку Upload New Submission. Она находится справа.



  8. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.



  9. Перейдите к той папке, где вы храните initials.c. Скорее всего, он находится в папке Downloads («Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете initials.c, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
  10. Кликните Add files ещё разок.
  11. Найдите caesar.c и откройте его.
  12. Проделайте то же самое для файла vigenere.c.
  13. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
  14. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.
  • ,

Пятая лекция CS50 уже на JavaRush [на русском!]

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

Каждый год примерно 3% студентов Гарвардского курса по основам программирования CS50 пытаются смошенничать во время учёбы, например, выдав чужой код за свой. Этой статистикой David Malan поделился на пятой лекции CS50. Представляете, какой процент был бы в наших вузах?.. Впрочем, не будем о грустном, давайте лучше о знаниях. Вот что вам расскажут в текущей лекции:

cs50 5 лекция

  • Баги. Без этих верных спутников разработчиков никуда не деться, нужно научиться их выискивать. Дэвид расскажет о некоторых типах багов. Начнет с тех, которые сложнее выцепить: логических;
  • Откровение: бесконечный цикл на самом деле не такой уж и бесконечный;
  • Функциональная декомпозиция: прием для повышения читаемости кода и удобства кодирования;
  • Знай свои фигурные скобки: область действия переменных;
  • Объявление функций до реализации: специально для C;
  • Строки и как с ними работать;
  • Что такое ошибка сегментации;
  • Милые щеночки! В стриме. Не пропустите=).
  • Как едят шоколадки и M&M’s в Гарварде. Наглядное пособие.

… ну а следующая лекция будет еще интереснее: молочное чудо Ovaltine и криптография. Одно только звучание завораживает!
  • ,

Гарвард CS50: задания первой недели (лекции 3 и 4)

CS50 задания

Друзья, основные теоретические сведения вы можете почерпнуть из конспекта семинаров. Там, помимо основ С рассказано, как подключиться к специальной облачной IDE CS50 (это нужно сделать для выполнения и проверки заданий), описаны основные нужные команды Linux и структуры языка. Если вам будет недостаточно материала о C, изложенного в лекции и конспекте, обратитесь к другим источникам. Например, к тем, что указаны в конце данной статьи.

В топике "Дополнительные материалы"
  • Цели первой недели
  • IDE CS50
  • Командная строка и обновление рабочей среды
  • Работа в IDE
  • Hello, C!
  • Баги?
  • Проверка на правильность: тест check50
  • Основы С: сравнение со Scratch
  • Основные типы данных в C
  • Библиотеки С
  • И снова Hello C: разбор синтаксиса простейших программ
  • Еще немного о вводе/выводе в C
Материалы в этом топике:

Ввод данных с проверкой: специальные функции библиотеки cs50.h
Для более удобного прохождения этого курса, мы разработали специальную библиотеку CS50, в которой, в частности, есть очень полезные функции обработки введенных пользователем данных.

GetString() считывает введенную пользователем строку
GetInt() считывает введенную пользователем строку и проверяет, не записано ли в ней целое число
GetFloat()считывает введенную пользователем строку и проверяет, не записано ли в ней число с плавающей точкой
GetLongLong() считывает введенную пользователем строку и проверяет, не записано ли в ней длинное вещественное число.

Задание 1. Умный подсчет расхода воды



Логично: чем дольше вы принимаете душ, тем больше воды уходит на этот процесс. Давайте прикинем, сколько? Даже если ваш душ едва открыт, в минуту из него вытекает примерно 6 литров воды. А это 12 бутылочек воды, которые вы носите с собой для питья. Обычно человек принимает душ минут 10. Итого, чтобы помыться, нужно 120 полулитровых бутылок. Немало!

Создайте файл water.c в вашей директории ~/workspace/pset1. Программа должна подсчитывать сколько бутылочек воды уходит на душ зависимости от времени. То есть:

  1. Программа запрашивает у пользователя количество минут, проведенных в душе
  2. Пользователь вводит положительное целое число
  3. Программа выводит на экран количество бутылочек, израсходованных пользователем.

username:~/workspace/pset1 $ ./water
minutes: 10
bottles: 120

Для простоты в этот раз мы будем считать, что пользователь всегда вводит число минут верно, то есть, мы не проверяем, было ли введено положительное и целое число. Позднее мы научимся писать проверки, но пока достаточно и этого.

Чтобы проверить правильность выполнения программы с помощью check50, нужно ввести следующую строку в терминале:

check50 2015.fall.pset1.water water.c

А если вы хотите посмотреть, как работает программа water, написанная сотрудниками курса выполните следующую команду:

~cs50/pset1/water


Задание 2. С нами Марио!


Знаете ли вы самого знаменитого водопроводчика в мире? С легкой руки компании Nintendo вымышленный усатый и немного полноватый дядечка в красной кепке стал героем для нескольких поколений геймеров. Если вы не знаете, о ком речь, вот вам ссылка на классическую игру 1985 года: поверьте, она всё ещё хороша и заслуживает внимания! Также можно найти вариант классического Super Mario для смартфонов или оффлайновых эмуляторов. Всё это нам нужно для общего развития, это еще, к сожалению, не задание;). А задание состоит вот в чем. В конце первого уровня Mario каждый игрок видел вот такую полупирамидку:

Создайте файл mario.c в вашей директории ~/workspace/pset1. Наша рограммка будет рисовать полупирамиду, подобную той, что вы видите, но прямо в консоли, без графики: каждый из блоков будет состоять из значка хэша (#). Даже если вы еще не сообразили, как это сделать, поверьте: это просто. Чтобы сделать задачу более интересной, добавим в неё возможность задавать высоту полупирамидки с помощью неотрицательного целого числа от 0 до 23. Высота пирамидки на картинке считается в самом высоком месте, то есть равна 8. Если пользователь неправильно вводит число, нужно попросить его сделать это ещё раз. Затем сгенерировать (с помощью printf пирамидку.

Озаботьтесь тем, чтобы выровнять нижний левый угол вашей полупирамиды по левому краю окна терминала, как в примере ниже. Подчеркнутый текст — это то, что пользователь вводит самостоятельно.

username:~/workspace/pset1 $ ./mario

height: <u>8</u>
       ##
      ###
     ####
    #####
   ######
  #######
 ########
#########

Обратите внимание, что два крайних правых столбца имеют одинаковую высоту. Генерировать трубы, облака и самого Марио пока не стоит=). По крайней мере для этого задания.

Если пользователь ввел неправильные данные (ввел не число, или число, которое меньше единицы или больше, чем 23), программа должна снова попросить его ввести данные, как в примере внизу, где подчеркнутый текст — то, что вводил пользователь с клавиатуры.

Для считывания введенной строки используйте GetInt. Она может помочь проверить неправильный ввод, но не для всех случаев.

username:~/workspace/pset1 $ ./mario
Height: -2
Height: -1
Height: foo
Retry: bar
Retry: 1
##

Чтобы скомпилировать программу, введите строку в терминале:

make mario

или более прозрачный, но длинный вариант:

clang -o mario mario.c -lcs50

после этого запустите программу на исполнение:

./mario

Если вы хотите проверить правильность выполнения программы, запускайте check50:

check50 2015.fall.pset1.mario mario.c

А если вы хотите поиграться с версией mario, созданной ассистентами курса, mario набирайте следующую строку:

~cs50/pset1/mario


Задание 3. Время получать сдачу

В наших широтах мы такого не встречали, а в США, похоже, есть такая вот игрушка, изображенная на фото: цилиндры предназначены для монет разного диаметра (и номиналов), выдает их пружинный механизм, а сам агрегат можно закрепить на поясе ребенка-кассира.

Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (NIST) всегда находят оптимальное решение на каждом шаге решения задачи, допуская, что конечное решение (полученное из совокупности таких шагов) также будет оптимальным.

Что это значит? Представим, что кассир должен покупателю сдачу в 41 цент, а у него на поясе есть цилиндры с монетками для сдачи номиналом в 25, 10, 5 и 1 цент. Руководствующийся «жадным» алгоритмом кассир сразу же захочет выдать максимум, на первом же шаге. На этом шаге оптимальным или наилучшим решением будет выдать 25 пенсов. 41-25 = 16. Осталось выдать 16 пенсов. Очевидно, 25 пенсов слишком много, значит, остается 10. 16-10 = 6. Теперь выдаем по тому же принципу 5 пенсов, и затем — 1. Таким образом, покупатель получит всего четыре монеты номиналом 25, 10, 5 и 1 пенс.

Оказывается, «жадная» пошаговая инструкция выдачи денег оптимальна не только для этого случая, но также для номиналов валюты США (и Евросоюза тоже). То есть, если у кассира достаточно монет любого номинала, алгоритм будет работать лучшим образом, то есть, выдаст минимальное количество монет из всех возможных случаев.
Итак, какое минимальное количество монеток нам нужно, чтобы дать сдачу? Это и есть наша третья задачка.

Создайте файл greedy.c в своей директории ~/workspace/pset1.

Дано: монетки номиналом 25, 10, 5, 1 цент

Программа должна:

  1. Спросить пользователя, сколько сдачи нужно выдать
  2. Посчитать минимальное количество монет, с помощью которых можно это сделать

Примечание: для ввода будем пользоваться функцией GetFloat из библиотеки CS50 и printf из стандартной библиотеки ввода/вывода для вывода. Кроме того, программа должна проверять корректность ввода.

Мы попросили вас использовать GetFloat, чтобы пользователь мог вводить значение в долларах и центах через точку. Например, если мы должны $9.75, пользователь должен ввести 9.75, но не $9.75 или 975.

Вы должны проследить, чтобы пользователь ввел число, которое имеет смысл. Скажем, неотрицательное, в этом функция GetFloat сама по себе не поможет. Если пользователь сделал неправильный ввод, нужно просить его повторить его и выполнять программу только с корректными данными.

Остерегайтесь неточностей, свойственных числам с плавающей точкой. Например, 0.01 не может быть представлено непосредственно как float. Попробуйте использовать форматированный вывод, например, с 50 знаками после запятой, используя указанный ниже код:

float f = 0.01;
printf("%.50f\n", f);

Кстати, перед тем, как что-либо считать, будет логично перевести всю сумму в центы, (и заодно преобразовать её из float в int), что поможет избежать массы ошибок и сложностей.
Чтобы наш автоматический анализатор кода мог правильно проверить вашу задачу, убедитесь, что последняя строка вывода вашей программы не содержит никакой другой информации, кроме минимального количества монеток: целое число с символом \n после него (те, кто учится на JavaRush, прекрасно знают, о чём мы здесь говорим =)).

Ниже — пример, как должен выглядеть результат работы вашей программы.

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
0.41
4

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

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
-0.41
How much change is owed?
-0.41
How much change is owed?
foo
Retry: 0.41
4

Исходя из этих требований и примера, который вы увидели выше, ваш код, скорее всего, должен содержать какой-то цикл.

Если во время тестирования приложения вы поймете, что цикл не останавливается, вы можете прервать выполнение программы комбинацией ctrl-c (иногда — многократной).

Как компилировать и выполнять программу вы уже знаете.

Если вы хотите проверить правильность работы вашей программы, с помощью утилиты check50, в терминале введите следующую строку:

check50 2015.fall.pset1.greedy greedy.c

А если вам захочется поиграть с этой программой, выполненной ассистентами курса, пропишите следующую команду:

~cs50/pset1/greedy

Как подтвердить правильность кода и получить оценки

Вариант 1

Если вам важно проверить именно правильность кода, а не получить итоговую оценку, вы можете его проверять и исправлять с помощью команды

check50 2015.fall.pset1.name name.c


введенной в терминальной строке CS50 IDE.
Где name — название файла вашей задачи.

Вариант 2
Если же вы хотите получить оценки (по сути, тот же запуск check50, но с запоминанием результата и заполнением некоторых форм на английском, тогда проделайте следующие шаги:
Шаг 1 из 2

  1. Когда приложения готовы, залогиньтесь в CS50 IDE.
  2. В левом верхнем углу CS50 IDE в пределах его файлового браузера, а не терминального окна, кликните левой клавишей мыши с удержанием ctrl или правой клавишей мыши по вашему файлу hello.c (тому, который лежит в директории pset1 ) и нажмите Download. Вы должны обнаружить, что браузер загрузил hello.c.
  3. Повторите для water.c.
  4. Повторите для mario.c.
  5. Повторите для greedy.c.
  6. В отдельной вкладке или окне залогиньтесь в CS50 Submit.
  7. Нажмите Submit в левом нижнем углу окна.
  8. Под Problem Set 1 на появившемся окне нажмите на Upload New Submission.
  9. На появившемся окне жмите Add files…. Должно появиться окно с именем Open Files.
  10. Пройдите путь к месту, куда загружен hello.c. Обычно он находится в папке Downloads или в той папке, которая назначена у вас по умолчанию для загрузки. Найдя hello.c, нажмите на него один раз чтобы отметить, затем нажмите Open.
  11. Кликните Add files… снова, и окно Open Files снова появится.
  12. Теперь найдите таким же образом файл water.c. Кликните по нему, затем кликните Open (или «Открыть»).
  13. Теперь находите mario.c. И тоже кликайте и открывайте таким же образом.
  14. Все то же самое с файлом greedy.c.
  15. Нажмите Start upload чтобы начать загрузку ваших файлов на серверы CS50.
  16. На появившемся экране вы увидите окно с надписью No File Selected. Если вы переместите курсор мыши в левую часть окра, вы увидите список файлов, которые вы загрузили. Нажмите на каждый, чтобы подтвердить содержание каждого из них. (Нет необходимости нажимать на другие кнопки или иконки). Если уверены, что готовы отослать файл на проверку, считайте, вы все сделали! Если хотите проверить свой код самостоятельно ещё раз или исправить что-либо, возвращайтесь в CS50 Submit и повторите эти шаги. Вы можете повторно отправить столько раз, сколько вы хотите; оцениваться будет только самое последнее представление.

Шаг 2 из 2
(он не обязателен для оценки, если что=))
Теперь перейдите по ссылке http://cs50.edx.org/2016/psets/1/ где вы обнаружите специальные формы. В них нужно ответить на несколько теоретических вопросов, и затем нажать Submit под ними.

Вопросы со звездочками – обязательны:

  • Alright, should've seen this one coming! In just a few sentences, what's a library? * (Кратко опишите, что такое библиотека)
  • In just a few sentences, what role does
    #include <cs50.h>

    play when you write it atop some program? *(какова роль строки #include <cs50.h>, которая фигурирует в верхней части кода некоторых программ?)
  • About how many hours would you say you spent on Problem Set 0: Scratch?(сколько времени у вас заняли задачки нулевой недели (Scratch)
  • About how many hours would you say you spent on Problem Set 1: C?(как долго вы решали задачки первой недели по C?)
  • What's your opinion of CS50x thus far? *(Ваше мнение о CS50 в настоящий момент, выбрать вариант нравится-не нравится)
  • Have you asked for help from classmates or staff via CS50s Facebook Group at www.facebook.com/groups/cs50? *(обращались ли вы за помощью к другим студентам или ассистентам в группе facebook)
  • Have you asked for help from classmates or staff via CS50s Subreddit at www.reddit.com/r/cs50 *(обращались ли вы за помощью к другим студентам или ассистентам через Subreddit)
  • Have you asked for help from classmates or staff via Twitter using @cs50 or #cs50? *(просили ли вы помощи у других студентов или ассистентов в Twitter используя @cs50 или #cs50).


Друзья, если возникают какие-то вопросы, пишите их в комментариях под этим руководством. Если вы не достигли пятого уровня JavaRush, чтобы получить приглашение на info, рекомендуем это сделать. Это бесплатно, интересно и не очень сложно.

Ресурс кода:

Лекция три
cdn.cs50.net/2015/fall/lectures/1/w/src1w.zip
Лекция четыре
cdn.cs50.net/2015/fall/lectures/1/f/src1f.zip
cdn.cs50.net/2015/fall/lectures/1/f/src1f/

Дополнительная литература

cpp.com.ru/kr_cbook/ — русская версия классической книги по C от авторов языка — Брайана Кернигана и Дэнниса Ритчи. Широко известна в узких кругах как K&R. Перевод, правда, не самого нового издания.
Почитайте первые три главы. Там будет несколько больше материала, чем вам нужно, но достаточно для решения задач.
computer.howstuffworks.com/c.htm — ресурс, рекомендуемый авторами CS50. На английском языке. Стр. 1-7, 9 и 10.