Лекція 1

• Минулого тижня
• C
• CS50 Sandbox
• Додаткові приклади
• Додаткові задачі

Минулого тижня

• Ми вже дізналися, що завдяки безлічі рівнів абстрагування та тим, хто до нас займався цією темою, ми можемо легко писати програми, які в остаточному підсумку будуть просто двійковими, 0 і 1.
• Розв’язання задачі можна описати як прийом вхідних даних (задачі) та використання алгоритму для пошуку вихідних даних (розв’язку).
• Комп'ютери представляють вхідні та вихідні дані за допомогою значної кількості бітів, двійкових цифр, 0 та 1, що увімкнені або вимкнекні. Із достатньою кількістю бітів ми можемо представляти не тільки великі числа, а й текст, зображення та відео.
• Можна використати різні алгоритми, які будуть розв’язувати одну і ту саму задачу, але з різним часом виконання.
• Ми можемо запусувати алгоритми точніше за допомогою псевдокоду, а також використовувати концепції функцій, циклів та умов.
  • За допомогою добровольців в аудиторії ми зробили бутерброди з арахісовим маслом та желе, хоча кожен з нас інтерпретував інструкції по-різному!
• Виявляється, ми (люди), природно, робимо припущення та абстракції під час виконання інструкцій або навіть псевдокоду. Але, як ми бачили в мові програмування Scratch, а також побачимо в мові програмування С, тепер так робити не вдасться, і нам доведеться думати уважніше про кроки та випадки, з якими доведеться працювати нашим програмам.
  • Завдяки Scratch ми скористались напрацюваннями хлопців з MIT, які створили блоки та спрайти для створення власних програм. І ми також зробили власні блоки, такі як функція cough («кашель), це була наша власна абстракція.

C

• Ми будемо використовувати нову мову C – це повністю текстова мова, яка містить складні службові слова та пунктуацію:

  #include <stdio.h>
  
  int main(void)
  {
      printf("hello, world\n");
  }
  

  • Це еквівалентно блоку «коли натиснуто зелений прапорець» та «сказати «Привіт, світ!»:
    
• Ми можемо порівняти багато конструкцій в мові програмування C з блоками, які ми вже бачили та використовували у Scratch. Синтаксис тут грає значно меншу роль, ніж принципи, з якими ми вже ознайомилися.
• Блок «Сказати «Привіт, світ!» - це функція, вона відповідає printf("hello, world\n");. У C функція виводу на екран виглядає як printf, де f означає «форматування», тобто ми можемо форматувати рядок різними способами. Потім ми використовуємо круглі дужки, щоб передати те, що ми хочемо вивести. Використовуються подвійні лапки, щоб виокремити текст або рядок і додати \n що означає новий рядок на екрані. (Наступного разу, коли ми використаємо функцію printf, наш текст буде розташований у новому рядку). Нарешті, ми додаємо крапку з комою ; щоб закінчити цей рядок коду в C.
• Блок «встановити [counter] у (0)» створює змінну, а в C ми б сказали int counter = 0;, де int вказує, що тип нашої змінної є цілим числом:
  
• «Змінити [counter] на (1)» — це counter = counter + 1; в C. (У C = не є знаком «дорівнює», де ми стверджуємо, що counter це те ж, що і counter + 1. На відміну від цього, = означає «скопіювати значення праворуч у значення ліворуч».) Можна також сказати counter += 1; або counter++; обидва з яких — «синтаксичний цукор», скорочення, що дозволяє писати менше слів чи знаків, але виконувати ті самі речі.
  
• Умова буде відповідна до:
  

  if (x < y)
  {
      printf("x is less than y\n");
  }
  

  • Зверніть увагу, що в C ми використовуємо фігурні дужки { і } (а також відступи) щоб вказати, як мають бути вкладені рядки коду.
• Також можливі умови «if-else» (якщо-інакше):
  

  if (x < y)
  {
      printf("x is less than y\n");
  }
  else
  {
      printf("x is not less than y\n");
  }
  

  • З іншого боку, пробіли, нові рядки та відступи, як правило, не є синтаксично важливими в C, тобто вони не впливають на те, як наша програма в кінцевому підсумку працює, але для нашого коду дуже важливо дотримуватися домовленостей і мати гарний «стиль», аби код був читабельним для людей.
• І навіть else if:
  

  if (x < y)
  {
      printf("x is less than y\n");
  }
  else if (x > y)
  {
      printf("x is greater than y\n");
  }
  else if (x == y)
  {
      printf("x is equal to y\n");
  }
  

  • Зверніть увагу, для порівняння двох значень у мові програмування C ми використовуємо ==, два знаки дорівнює.
  • Отже, за логікою, нам не потрібно if (x == y) в останній умові, оскільки це єдиний випадок, що лишився, і ми можемо просто використати else.
• Цикли можна задавати ось так:
  

  while (true)
  {
      printf("hello, world\n");
  }
  

  • Ключове слово while (поки) також вимагає певної умови, тому ми використовуємо true (істина) як булевий вираз, аби переконатися, що наш цикл буде працювати постійно. Наша програма перевірить, чи значення виразу вираховується як true (в цьому випадку це завжди істина), а потім запустить рядки всередині фігурних дужок. А потім буде повторюватися доти, поки вираз не перестане бути істинним (в цьому випадку він не зміниться).
    

    for (int i = 0; i < 50; i++)
    {
      printf("hello, world\n");
    }
    

  • Щоб написати цикл, який буде працювати визначену кількість разів, ми використовуємо ключове слово for і спочатку ми створюємо змінну i та присвоюємо їй значення 0. i традиційна назва для змінної, яка відстежує, скільки ітерацій циклів ми вже пройшли. Далі, ми перевіряємо, чи i < 50, щоразу, коли ми повертаємося вгору циклу, перш ніж запускати код усередині. Якщо цей вираз — true, ми запускаємо код всередині. Нарешті, після виконання коду, ми використовуємо i++ щоб додати одиницю до i, і цикл повторюється.
• Ми також можемо отримати вхідні дані від користувача:
  

  string answer = get_string("What's your name?\n");
  printf("%s\n", answer);
  

  • У Scratch, відповідь буде збережена у змінній, яка називається «answer», але в C ми можемо вказувати назву змінної. Ми також оберемо «answer», і тип цієї змінної string– це рядок, який представляє лише послідовність символів.
  • І ми будемо використовувати printf для виводу рядка, але нам потрібно вказати, як саме це робити. Спочатку ми передаємо "%s, рядок, який ми хочемо вивести, це і є %s. %s місцезаповнювач, який printf замінює значенням рядка, який ми передаємо далі і визначаємо як answer.
  • Також, нам знадобиться це, оскільки ми можемо тепер це конвертувати:
    

    string answer = get_string("What's your name?\n");
    printf("hello, %s\n", answer);
    

CS50 Sandbox

• CS50 Sandbox – це хмарне віртуальне середовище, де встановлено відповідні бібліотеки та налаштування для того, аби ми всі могли розпочати писати та запускати програми однаково. Зверху є простий редактор коду, де ми можемо вводити текст. Нижче вікно терміналу, в яке ми можемо вводити команди:
  
• Вводимо наш код вгорі:
  
  • o Зауважте, що наш код позначений кольором, це використовується для виділення тих чи інших речей у коді.
  • o Ми пишемо код та зберігаємо його у файл, щось на зразок hello.c, щоб вказати, що це написано мовою програмування C.
• Після збереження написаного нами коду, який називається вихідним кодом, ми повинні перетворити його на машинний код, тобто двійкові інструкції, які комп'ютеру легше зрозуміти.
  • Ми використовуємо програму під назвою компілятор, аби перетворити наш вихідний код у машинний код.
• Для цього ми використовуємо панель терміналу. Значок $ зліва – це запит командного рядка, куди ми можемо вводити команди.
• Ми набираємо clang hello.c (де clang означає «C languages») і … нічого не відбувається. Ми бачимо ще одну позначку $, очікуючи іншу команду. Ми можемо натиснути на значок теки у верхньому лівому кутку панелі CS50 Sandbox, і побачимо, що зараз ми маємо інший файл, який називається a.out. Тепер ми можемо набрати ./a.out у вікні терміналу та побачити hello, world. Щойно ми написали, скомпілювали та запустили нашу першу програму!
• Ми можемо змінити назву нашої програми з a.out на будь-яку іншу. Ми можемо передавати параметри командного рядка програмам в терміналі, якщо вони приймають їх. Наприклад, ми можемо набрати clang -o hello hello.c, і -o hello каже програмі clang зберегти вивід компілятора як файл hello. Тоді ми можемо просто запустити ./hello. (. означає поточну теку.)
• Ми можемо навіть абстрагуватись від цього, просто набравши make hello. Ми бачимо, що за замовчуванням (у CS50 Sandbox), make використовує clang для компіляції нашого коду з hello.c до hello, з іншими спеціальними переметрами.
• Тепер спробуємо отримати дані від користувача.

  #include <stdio.h>
  
  int main(void)
  {
      string name = get_string("What is your name?\n");
      printf("hello, name\n");
  }
  

  • Якщо під час запуску make hello, ми отримуємо багато помилок, варто піднятися вгору та подивитися, яка помилка трапилася першою, оскільки вона могла призвести до усіх наступних.
  • Ми бачимо, що першою помилкою є hello.c:5:5: error: use of undeclared identifier 'string' .... Це свідчить про те, що на рядку 5, символ 5, файла hello.c, компілятор виявив щось, що називається string і він це не розпізнав. Насправді мова програмування C не має типу, що називається string.
• Щоб спростити речі (принаймні, для початку), ми будемо включати бібліотеку або набір коду з CS50. Бібліотека надає нам тип змінної string, функцію get_string і багато іншого. Нам просто потрібно написати рядок у верхній частині, щоб включити файл cs50.h:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      string name = get_string("What is your name?\n");
      printf("hello, name\n");
  }
  

  • stdio.h – це бібліотека, яка розповсюджується разом з C, що означає «стандартний ввід/вивід», вона містить функцію printf яка виводить дані на екран.
• Тепер, якщо ми спробуємо скомпілювати цей код, наша перша помилка буде hello.c:6:12: error: unused variable 'name' .... Виявляється, ми не зробили нічого зі змінною name після її оголошення. Для цього нам потрібно змінити наступний рядок:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      string name = get_string("What is your name?\n");
      printf("hello, %s\n", name);
  }
  

  • Ми передаємо два аргументи, або параметри, до printf. Перший – це рядок, який ми хочемо вивести, з нашим місцезаповнювачем %s placeholder, and the second is the variable name, а другий – це ім'я змінної, яку ми хочемо передати до нього.
• Якщо ми змінюємо наш код, потрібно зберегти файл і запустити make hello ще раз. І якщо ми хочемо зупинити нашу програму до її завершення, нам просто потрібно натиснути control-C.
• Функції, такі як get_string або printf, можуть приймати аргументи. Вони також можуть повертати значення, а get_string повертає щось із типом string.

Додаткові приклади

• Бібліотека CS50 має інші функції для отримання вхідних даних різних типів:
  • get_char
  • get_double
  • get_float
  • get_int
  • get_long
  • get_string
  • …
• Існують відповідні типи в C і способи їх виводу за допомогою printf:
  • bool
  • char, %c
  • double
  • float, %f
  • int, %i
  • long, %li
  • string, %s
• CS50 Sandbox підтримує різноманітні мови, серед них ми можемо обрати, а ще можемо обрати назву файлу, з яким ми почнемо працювати.
• Насправді, ви можете натиснути на посилання до кожного із цих прикладів на сторінці завдань тижня для запуску та редагування своїх копій.
• У int.cми отримуємо та виводимо на екран ціле число:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      int i = get_int("Integer: ");
      printf("hello, %i\n", i);
  }
  

  • Зверніть увагу, що ми використовуємо %i для виводу цілого числа.
  • int main(void) є еквівалентом «натиснуто зелений прапорець». Про це ми дізнаємося більше в найближчих лекціях.
  • Тепер ми можемо запустити make int і запустити нашу програму командою ./int.
• У float.c ми отримуємо десяткове число (які називаються числа з рухомою комою, тому що десяткова кома може «рухатись» між цифрами, залежно від числа):

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      float f = get_float("Float: ");
      printf("hello, %f\n", f);
  }
  

  • Тепер, якщо ми компілюємо та запускаємо нашу програму, бачимо щось на зразок hello, 42.000000, навіть якщо ми просто набрали 42 у запиті командного рядка.
• З ints.c ми можемо трохи побавитись в математику:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt user for x
      int x = get_int("x: ");
  
      // Prompt user for y
      int y = get_int("y: ");
  
      // Perform arithmetic
      printf("x + y = %i\n", x + y);
      printf("x - y = %i\n", x - y);
      printf("x * y = %i\n", x * y);
      printf("x / y = %i\n", x / y);
      printf("x mod y = %i\n", x % y);
  }
  

  • Спочатку, ми отримуємо два цілих числа, x та y. Потім ми виводимо дію, яку хочемо виконати: x + y = %i\n, та передаємо туди значення, яке нам потрібно x + y. * використовується для множення, а / для ділення. % між двома змінними - це остача від ділення.
  • o Цікаво, що коли ми використовуємо 2 для x і 10 для y, то в результаті отримуємо … x / y = 0. Виявляється, оскільки обидві змінні – це цілі числа, результат – це ціле число, і оскільки 2 розділений на 10 менше за 1, все, що залишається, — це 0.
• З floats.c ми бачимо, що відбувається, коли використовуємо числа з рухомою комою:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt user for x
      float x = get_float("x: ");
  
      // Prompt user for y
      float y = get_float("y: ");
  
      // Perform division
      printf("x / y = %.50f\n", x / y);
  }
  

  • За допомогою %50f ми можемо вказати кількість десяткових знаків, які виводяться на екран.
  • Хм, і тепер ми отримуємо …

    x: 2
    y: 10
    x / y = 0.20000000298023223876953125000000000000000000000000
    

• Комп'ютер має пам'ять, яка знаходиться в апаратних чіпах, це оперативна пам’ять. Наші програми використовують цю пам’ять для зберігання даних під час їх виконання, але ця пам'ять обмежена. Тому з обмеженим числом бітів ми не можемо представити всі можливі числа (яких є нескінченна кількість). Отже, на нашому комп'ютері є певна кількість бітів для кожного числа з рухомою комою, і має округлювати їх до найближчого десяткового значення в певний момент.
• Ці неточності можуть стати реальною проблемою, коли йдеться про фінанси, ракети або в наукових програмах. Але ми можемо обійти цю проблему, вказавши кількість десяткових знаків для досягнення необхідної точності, і виділити необхідну кількість бітів для збереження саме цієї кількості десяткових знаків.
• Для чисел з рухомою комою у C більшість комп'ютерів використовують 4 байти або 32 біти. Інший тип, який називається double, використовує в два рази більше бітів, тобто 8 байт.
• Якщо ми запускаємо doubles.c, який є тим самим floats.c але з типом double для змінних, ми бачимо, що у нас набагато більше чисел після коми. І компроміс для додаткової точності полягає в тому, що тепер нам потрібно використати більше пам'яті.
• Розглянемо parity.c:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt user for integer
      int n = get_int("n: ");
  
      // Check parity of integer
      if (n % 2 == 0)
      {
          printf("even\n");
      }
      else
      {
          printf("odd\n");
      }
  }
  

  • Взявши остачу від ділення n на 2, можна визначити, чи n є парним чи непарним числом.
• У conditions.c, ми перетворюємо попередній фрагмент коду на програму:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt user for x
      int x = get_int("x: ");
  
      // Prompt user for y
      int y = get_int("y: ");
  
      // Compare x and y
      if (x < y)
      {
          printf("x is less than y\n");
      }
      else if (x > y)
      {
          printf("x is greater than y\n");
      }
      else
      {
          printf("x is equal to y\n");
      }
  }
  

• У answer.c, ми отримуємо текст від користувача:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      // Prompt user for answer
      char c = get_char("Answer: ");
  
      // Check answer
      if (c == 'Y' || c == 'y')
      {
          printf("yes\n");
      }
      else if (c == 'N' || c == 'n')
      {
          printf("no\n");
      }
  }
  

  • Тут ми використовуємо get_char та тип даних char щоб отримати один символ від користувача.
  • Зауважте, що ми використовуємо || щоб позначити «або» у нашому булевому виразі. (Логічне «і» буде позначатись &&.)
• У Scratch, ми створили власний блок, який ми назвали «cough» (кашель). Ми можемо зробити те ж саме в C, створивши власну функцію.
• Якщо ми хочемо вивести «cough» 3 рази, ми використовуємо цикл for:

  #include <stdio.h>
  
  int main(void)
  {
      for (int i = 0; i < 3; i++)
      {
          printf("cough\n");
      }
  }
  

• Ми можемо перемістити рядок з printf до власної функції:

  #include <stdio.h>
  
  void cough(void);
  
  int main(void)
  {
      for (int i = 0; i < 3; i++)
      {
          cough();
      }
  }
  
  // Cough once
  void cough(void)
  {
      printf("cough\n");
  }
  

  • Зверніть увагу, нам треба оголосити, що функція cough існує, тож нам потрібен її прототип, void cough(void); перед тим, як функція main буде її викликати. Компілятор C читає код згори до низу, тож нам треба сказати йому, що функція cough існує до того, як ми будемо її використовувати. Також, ми хочемо тримати нашу фугкцію main ближче до гори, тож фактична реалізація функції cough все одно буде внизу.
  • Фактично, cs50.h та stdio.h - заголовочні файли, що містять прототипи таких функцій, як get_string та printf, щоб ми могли їх далі використовувати. Фактична реалізація цих функцій знаходиться у cs50.c та stdio.c у вигляді вихідного коду, і вони скомпільовані у файли в іншому місці у системі.
  • Наша функція cough не приймає аргументів, тож ми пишемо cough(void), вона також нічого не повертає, тож маємо void перед cough також. (Наша фугкція main повертає int, і за замовчуванням вона поверне 0 якщо нічого поганого не трапиться.)
• Ми можемо абстрагувати cough ще більше:

  #include <stdio.h>
  
  void cough(int n);
  
  int main(void)
  {
      cough(3);
  }
  
  // Cough some number of times
  void cough(int n)
  {
      for (int i = 0; i < n; i++)
      {
          printf("cough\n");
      }
  }
  

  • Тепер, якщо ми хочемо вивести «cough» кілька разів, можна викликати ту саму функцію. Зверніть увагу, що за допомогою cough(int n), ми вказуємо, що функція cough приймає вхідні дані типу int, до яких ми звертаємось як n. І всередині cough ми використовуємо n у нашому циклі for для того, щоб вивести «cough» стільки разів, скільки потрібно.
• Розглянемо positive.c:

  #include <cs50.h>
  #include <stdio.h>
  
  int get_positive_int(string prompt);
  
  int main(void)
  {
      int i = get_positive_int("Positive integer: ");
      printf("%i\n", i);
  }
  
  // Prompt user for positive integer
  int get_positive_int(string prompt)
  {
      int n;
      do
      {
          n = get_int("%s", prompt);
      }
      while (n < 1);
      return n;
  }
  

  • У бібліотеці CS50 немає функції get_positive_int але ми можемо її написати самостійно. У нашій функції ми ініціалізуємо змінну, int n, але не поки присвоюємо їй значення. Далі маємо нову конструкцію, do ... while, що робить щось спочатку, потім перевіряє умову і повторює дію, поки умова не стане false.
  • Далі, коли ми маємо n, що не < 1, ми можемо використати ключове слово return щоб повернути значення. І знову в нашій функції main function, ми можемо присвоїти int i це значення.
  • У C змінні також мають область видимості, що, як правило, означає, що вони існують лише між тими фігурними дужками, де вони були оголошені. Наприклад, якщо б ми мали int n = get_int(...) ми не змогли б повернути її за допомогою return оскільки цей рядок був би не в межах області видимості n. (Аналогічно, наша функція main не може безпосередньо бачити будь-які змінні всередині get_positive_int, sоскільки кожна функція має свій набір фігурних дужок і, таким чином, має різні області видимості для змінних, що знаходяться всередині них.)
• У Scratch, можливо, ви помітили, що можете зробити змінну, яка буде доступна одному спрайту або відразу всім. І в C ми маємо як локальні, так і глобальні змінні. Усі змінні, які ми досі бачили, — локальні, хоча зрештою ми побачимо і глобальні змінні, які ми зможемо використати будь-де у нашій програмі.

Додаткові задачі

• Ми вже бачили приклад неточності з числами з рухомою комою, але можуть бути проблеми і з цілими числами.
• Якщо б, наприклад, у нас було число 129, до якого ми додали 1, ми не мали б 1210, де остання цифра змінилася з 9 на 10. Замість цього ми переносимо 1, таким чином, щоб одержати 130. І якщо б ми мали число 999, ми б перенесли 1 стільки разів, скільки треба було, щоб отримати число 1000.
• Але якщо у нас є місце для запису лише 3 цифр, вийшло б 000. Це називається переповненням, тобто число, яке ми намагаємося зберегти, занадто велике для обсягу пам’яті, який ми виділили.
• У двійковій системі, якщо б ми мали число 111, і додали 1, ми б переносили 1, поки не отримали 1000. І так само, якщо б ми мали тільки 3 біти, у нас було б 000.
• У грі Lego Star Wars встановлено максимум 4 мільярди монет, які гравець може зібрати, оскільки, мабуть, використовується лише 32 біти для збереження цього числа (2 у степені 32 – це трохи більше 4 мільярдів).
• Розглянемо це в overflow.c:

  #include <stdio.h>
  #include <unistd.h>
  
  int main(void)
  {
      // Iteratively double i
      for (int i = 1; ; i *= 2)
      {
          printf("%i\n", i);
          sleep(1);
      }
  }
  

  • Зверніть увагу, що тут є рядок, що починається з //, що означає коментар. Коментарі - це пояснення для себе або майбутніх читачів, які компілятор ігнорує.
  • У нашому циклі for lми встановили i до 1, і подвоїли її за допомогою *= 2. (І ми будемо продовжувати робити це постійно, оскільки немає заданої умови.)
  • Ми також використовуємо функцію sleep з unistd.h щоб програма щоразу робила паузу.
  • Тепер, коли ми запускаємо нашу програму, ми бачимо, що число стає все більшим і більшим, поки не станеться:

    1073741824
    overflow.c:9:31: runtime error: signed integer overflow: 1073741824 * 2 cannot be represented in type 'int'
    -2147483648
    0
    0
    ...
    

  • Виявляється, наша програма розпізнала, що знакове ціле число (число зі знаком + чи -) не змогло зберегти наступне значення і видала помилку. Далі, оскільки вона намагалася подвоїти число все одно, i стала негативним числом, а потім 0.
• Проблема Y2K («Проблема 2000 року») виникла через те, що багато програм зберігали календарний рік лише за допомогою двох цифр, таких як 98 для 1998 року та 99 для 1999. Але коли прийшов 2000 рік, програми мали б зберігати 00, що призвело б до плутанини між 1900 і 2000 роками.
• З літаком Boeing 787 також виникли труднощі, коли лічильник у генераторі переповнився через певну кількість днів безперервної роботи, оскільки кількість секунд, котрі він пропрацював, не могли більше зберігатися в цьому лічильнику.
• У старій версії гри Civilization, цілочисельне переповнення призводило до того, що один із персонажів, Ґанді, ставав набагато агресивнішим, оскільки рівень його агресії, від початку низький, ставав великим, коли від нього віднімали забагато. Наприклад, якщо б ми мали 00000001 і відняли 1 від нього, ми будемо мати 00000000. Але якщо нам доведеться відняти 2, ми фактично повертаємося назад на 11111111, що є найбільшим позитивним значенням!
• Отже, ми побачили труднощі, які можуть статися, але ми сподіваємося, що тепер також стало зрозуміло, чому та як їх уникати.
• Для завдань цього тижня ми використаємо CS50 Lab, побудовану на CS50 Sandbox, і напишемо кілька програм, аби розібратись у всьому.