JavaRush /Java блог /Архив info.javarush /Гарвард CS50: задания первой недели (лекции 3 и 4)
Masha
41 уровень

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

Статья из группы Архив info.javarush
Гарвард CS50: задания первой недели (лекции 3 и 4) - 1Друзья, основные теоретические сведения вы можете почерпнуть из конспекта семинаров. Там, помимо основ С рассказано, как подключиться к специальной облачной IDE CS50 (это нужно сделать для выполнения и проверки заданий), описаны основные нужные команды Linux и структуры языка. Если вам будет недостаточно материала о C, изложенного в лекции и конспекте, обратитесь к другим источникам. Например, к тем, что указаны в конце данной статьи. В топике "Дополнительные материалы"
  • Цели первой недели
  • IDE CS50
  • Командная строка и обновление рабочей среды
  • Работа в IDE
  • Hello, C!
  • Баги?
  • Проверка на правильность: тест check50
  • Основы С: сравнение со Scratch
  • Основные типы данных в C
  • Библиотеки С
  • И снова Hello C: разбор синтаксиса простейших программ
  • Еще немного о вводе/выводе в C
Материалы в этом топике:
  • Ввод данных с проверкой: специальные функции библиотеки cs50.h
  • Задание 1. Умный подсчет расхода воды
  • Задание 2. С нами Марио!
  • Задание 3. Время получать сдачу
  • Как подтвердить правильность кода и получить оценки
  • Ресурс кода
  • Дополнительная литература

Ввод данных с проверкой: специальные функции библиотеки cs50.h

Для более удобного прохождения этого курса, мы разработали специальную библиотеку CS50, в которой, в частности, есть очень полезные функции обработки введенных пользователем данных.
  • GetString() считывает введенную пользователем строку;

  • GetInt() считывает введенную пользователем строку и проверяет, не записано ли в ней целое число;

  • GetFloat()считывает введенную пользователем строку и проверяет, не записано ли в ней число с плавающей точкой;

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

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

Гарвард CS50: задания первой недели (лекции 3 и 4) - 2Логично: чем дольше вы принимаете душ, тем больше воды уходит на этот процесс. Давайте прикинем, сколько? Даже если ваш душ едва открыт, в минуту из него вытекает примерно 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. С нами Марио!

Гарвард CS50: задания первой недели (лекции 3 и 4) - 3Знаете ли вы самого знаменитого водопроводчика в мире? С легкой руки компании Nintendo вымышленный усатый и немного полноватый дядечка в красной кепке стал героем для нескольких поколений геймеров. Если вы не знаете, о ком речь, вот вам ссылка на классическую игру 1985 года: поверьте, она всё ещё хороша и заслуживает внимания! Также можно найти вариант классического Super Mario для смартфонов или оффлайновых эмуляторов. Всё это нам нужно для общего развития, это еще, к сожалению, не задание;). А задание состоит вот в чем. В конце первого уровня Mario каждый игрок видел вот такую полупирамидку: Создайте файл mario.c в вашей директории ~/workspace/pset1. Наша рограммка будет рисовать полупирамиду, подобную той, что вы видите, но прямо в консоли, без графики: каждый из блоков будет состоять из значка хэша (#). Даже если вы еще не сообразили, как это сделать, поверьте: это просто. Чтобы сделать задачу более интересной, добавим в неё возможность задавать высоту полупирамидки с помощью неотрицательного целого числа от 0 до 23. Высота пирамидки на картинке считается в самом высоком месте, то есть равна 8. Если пользователь неправильно вводит число, нужно попросить его сделать это ещё раз. Затем сгенерировать (с помощью printf пирамидку). Озаботьтесь тем, чтобы выровнять нижний левый угол вашей полупирамиды по левому краю окна терминала, как в примере ниже. Подчеркнутый текст — это то, что пользователь вводит самостоятельно.

username:~/workspace/pset1 $ ./mario

height: 8
       ##
      ###
     ####
    #####
   ######
  #######
 ########
#########
Обратите внимание, что два крайних правых столбца имеют одинаковую высоту. Генерировать трубы, облака и самого Марио пока не стоит=). По крайней мере для этого задания. Если пользователь ввел неправильные данные (ввел не число, или число, которое меньше единицы или больше, чем 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. Время получать сдачу

Гарвард CS50: задания первой недели (лекции 3 и 4) - 4В наших широтах мы такого не встречали, а в США, похоже, есть такая вот игрушка, изображенная на фото: цилиндры предназначены для монет разного диаметра (и номиналов), выдает их пружинный механизм, а сам агрегат можно закрепить на поясе ребенка-кассира. Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (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. Вариант 1

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

    
    check50 2015.fall.pset1.name name.c
    

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

  2. Вариант 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 и повторите эти шаги. Вы можете повторно отправить столько раз, сколько вы хотите; оцениваться будет только самое последнее представление.
  3. Шаг 2 из 2 (он не обязателен для оценки, если что=))

    Теперь перейдите по ссылке https://www.edx.org/course/cs50s-introduction-computer-science-harvardx-cs50x где вы обнаружите специальные формы. В них нужно ответить на несколько теоретических вопросов, и затем нажать 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 http://www.facebook.com/groups/cs50? *(обращались ли вы за помощью к другим студентам или ассистентам в группе facebook)
  • Have you asked for help from classmates or staff via CS50s Subreddit at http://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, рекомендуем это сделать. Это бесплатно, интересно и не очень сложно.

Ресурс кода:

  1. Лекция три

    http://cdn.cs50.net/2015/fall/lectures/1/w/src1w.zip

  2. Лекция четыре

    http://cdn.cs50.net/2015/fall/lectures/1/f/src1f.zip

    http://cdn.cs50.net/2015/fall/lectures/1/f/src1f/

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

http://cpp.com.ru/kr_cbook — русская версия классической книги по C от авторов языка — Брайана Кернигана и Дэнниса Ритчи. Широко известна в узких кругах как K&R. Перевод, правда, не самого нового издания. Почитайте первые три главы. Там будет несколько больше материала, чем вам нужно, но достаточно для решения задач. https://computer.howstuffworks.com/c.htm — ресурс, рекомендуемый авторами CS50. На английском языке. Стр. 1-7, 9 и 10.
Комментарии (51)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Kirill Lvov Уровень 1
3 августа 2019
вот мой

#include <iostream>
#include <stdio.h>

using namespace std;

double Money;
int Cents;

int main()
{	
	cout << "how mush you want to exchange ";
	cin >> Money;
	int Cents = Money * 100;
	int Counter = 0;
	cout << Cents << endl;

	while (Cents >= 25)
	{
		Cents = Cents - 25;
		Counter++;
	}
	while (Cents >= 10)
	{
		Cents = Cents - 10;
		Counter++;
	}
	while (Cents >= 5)
	{
		Cents = Cents - 5;
		Counter++;
	}
	while (Cents >= 1)
	{
		Cents = Cents - 1;
		Counter++;
	}
	cout << Counter;
}

Vitaly Repkin Уровень 1
21 марта 2019
Сейчас cs50.io не работает, есть какие то аналоги??
Ilya Mikhailov Уровень 0
16 сентября 2018
Мой вариант решения задачи с кредитными картами

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

int main(){
    long long cc = get_long_long("Number: ");
    int type = 0, sum = 0;

    if( cc > 34*(pow(10,13)) && cc < 38*pow(10,13)-1 ) {
        type = 1;       //cc amex
    } else if( cc > 4*pow(10,15) && cc < 5*pow(10,15)-1 ) {
        type = 2;       //cc visa
    } else if( cc > 51*pow(10,14) && cc < 56*pow(10,14)-1 ) {
        type = 3;       //cc ms
    }

    while(cc != 0) {
        sum += cc%10;
        cc /= 10;

        if ( 2*(cc%10) < 10 ) {
            sum += 2*(cc%10);
        } else {
            sum += 1+(2*(cc%10))%10;
        }
        cc /= 10;
    }

    if (sum%10 != 0) {
        type = 0;
    }

    switch(type) {
        case 1:
        printf("AMEX\n");
        break;

        case 2:
        printf("VISA\n");
        break;

        case 3:
        printf("MASTERCARD\n");
        break;

        default:
        printf("INVALID\n");
        break;
    }

}
Ohr Уровень 5
1 сентября 2016
Всем привет! Подскажите что за бред почему компилятор матюкая меня, говорит что это выражение
while (1 < h < 24);
может вернуть только
true
?
zeffir4ik Уровень 8
31 августа 2016
И снова всем привет!
Возвращаюсь к своим баранам. Моя проверка кредиток работает не правильно и я не могу понять где ошибка. Вернее я, по всей видимости, не правильно понимаю как должен работать алгоритм. Например 4111111111111111 должно определятся как VISA. Ок. Как это вижу я (и собственно как реализован мой алгоритм)
1) Берем все вторые числа и умножаем каждое на 2 ( 1*2=2, 1*2=2, 1*2=2, 1*2=2, 1*2=2, 1*2=2, 1*2=2, 1*2=2)
2) Складываем все полученные числа (если число бошьше 10 то его разбираем по разрядно и сначала складываем то чтополучилось (напр. 15 = 1 + 5 + 6)). Для нашего условия (2+2+2+2+2+2+2+2 = 16)
3) Складываем все нечетные элементы первоначального числа (4+1+1+1+1+1+1+1 = 11)
4) Складываем результаты двух сложений (16 + 11 = 27)
5) Если результат делится на 10 без остатка — значит это валидная VISA (в нашем примере)

НО 27 никак не делится на 10 без остатка. То есть одно из двух: либо это не валидная ВИЗА, либо я не правильно понимаю алгоритм.

Подскажите кто поумнее, а?
zeffir4ik Уровень 8
20 августа 2016
Ку всем!) А кто-нить делал задачи из «хакерского» задачника? Конкретно интересует задача про номера кредиток. Задайте направление. Как для начала в ней реализовать вычленение каждой второй цифры? Ведь я так понимаю пользователь должен ввести все цифры разом и мы должны записать это в единую переменную long? Или я куда-то не туда смотрю?
skalapendro Уровень 10
2 августа 2016
У этого курса на edx есть дедлайны? А то я с английским пока не очень…
nyamkas Уровень 7
29 июля 2016
Как получить оценки?, при попытке перейти на CS50 Submit пишет:
403 You don't have permission to do that!
Tigran Уровень 30
29 июля 2016
Фуф, доделал Марио) Правда, прежде чем начать делать пирамидку, убил минут 30 на ту самую игру :)
Сначала тоже делал с помощью 2 циклов, расставления пробелов и т.д., потом:
1. нашел интересную функцию, «не имеюющую аналогов в мире»™ — strncat(s1, s2, i) — это позволило избавиться от 1 цикла.
2. нашел классную фишку в printf — знак *
3. минут 20 промурыжился с ошибкой Segmentation fault. Оказалось, что в C нелья просто так взять и конкатенировать строки, как в джаве, злобный компилятор не даст ни грамма лишней памяти :) Решилось через объявление максимального размера при инициализации переменной — char string[40] = "##";

В общем, что-то мне все это напоминает… задачка на 5 строк, а времени 2 часа :) Где-то я все это уже видел…
Pex1k Уровень 24
27 июля 2016
Здравствуйте. На счет третьего задания.
Сделал цикл, проверяю с помощью команды «check50 2015.fall.pset1.greedy greedy.c». Все верно, но для числа 4.2 выводится неточный ответ (должен быть 18, а у меня 22). Стал разбираться из-за чего. После того, как я из долларов (4.2) перевожу в центы, должно быть 420 центов, но почему-то именно данное число (я проверял) меняется на 419. Вот кусочек, где я меняю из долларов в центы. x — центы.