Компьютерный журнал айтишника

Продолжаем курс cs50, неделя третья, алгоритмы сортировки. Настало время лабораторки. Она очень простая:

• скачать тестовый сетап: https://cdn.cs50.net/2021/fall/labs/3/sort.zip
• внутри архива лежат три уже скомпилированные программы на C: sort1, sort2 и sort3 — это бинарники, т.е. файлы с двоичным кодом, поэтому мы не можем просмотреть их исходный код на C.
• каждая из этих программ работает по одному из алгоритмов сортировки: сортировка выбором (selection sort), пузырьковая сортировка (bubble sort) или сортировка слиянием (merge sort). В каком файле какая — мы не знаем. Наша задача — определить, какой алгоритм сортировки используется в каждом бинарнике.

Читать далее →

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

1. печать чисел от 1 до n
2. печать четных/нечетных чисел до n
3. возведение n в степень
4. печать n! (факториал — произведение чисел до n)
5. печать суммы чисел от n до m
6. печать чисел Фибоначчи (каждое следующее — сумма двух предыдущих)
7. печать чисел Коллатца (чётное: n/2; нечетное: n*3+1)
8. копирования строки из одной в другую
9. печать элементов массива
10. печать строки наоборот
11. конвертация десятичного числа в двоичное
12. бинарный поиск
13. сортировка «пузырьком»
14. сортировка слиянием

Читать далее →

Продолжаем проходить курс Computer Science CS50 и язык C. Изучаем рекурсию на примере гипотезы Коллатца — интересной (и простой для понимания) математической проблемы, которая все еще не решена учеными.

Гипотеза Коллатца:

1. Возьмем любое положительное целое число
2. Если оно чётное, то поделим его на 2
3. Если нечётное, то  умножаем на 3 и прибавляем 1 (получаем n * 3 + 1).
4. Далее полученное число снова оцениваем — четное оно или нет и снова  выполняем те же самые действия, до тех пор, пока не получим 1.

Итого, суть гипотезы Коллатца в том, что абсолютно любое число при применении к нему этих двух простых операций рано или поздно превратится в 1. Читать далее →

На третьей неделе курса Computer Science CS50 (Harvard) предлагается выполнить домашнее задание в Problem Set 3 под названием runoff.c — нужно написать код программы, которая не просто подсчитывает, какой кандидат набрал наибольшее количество голосов, как в прошлый раз, в программе runoff нужно реализовать голосование до набора более 50% голосов всех избирателей.

Победитель будет объявлен только тогда, когда один из кандидатов наберет более половины голосов. Чтобы это можно было сделать, каждый голосующий ранжирует всех кандидатов от наибольшего предпочтения (ранг 1) до наименьшего (последний ранг). Далее подсчитывается сумма голосов в первом туре (ранг 1). Если кто-то из кандидатов наберет на этом этапе более 50% голосов, его объявляют победителем. Читать далее →

Начинается третья неделя обучения Computer Science CS50 (Гарвард) и мы продолжаем учить язык C. Первое задание: реализация системы голосования, где выигрывает кандидат, получившей наибольшее количество голосов, т.н. мажоритарная система по большинству или просто «победитель получает все» (plurality.c). Пользователь может выбрать из списка кандидатов одного и проголосовать за него. При подсчете голосов, кандидат, набравший наибольшее количество голосов, объявляется победителем выборов.

Читать далее →

На второй неделе обучения по курсу Computer Science CS50 (Harvard) после выполнения всех индивидуальных заданий мы переходим к лабораторной работе по языку C, которую нужно выполнять в группе. Это будет интересная задача — написать код игры «Эрудит» (Scrabble.с). Суть задания: игроки придумывают слова, которые набирают разное количество очков в зависимости от букв в этом слове, при этом каждой букве приписывается разное количество очков от 1 до 10 и затем эти очки складываются (сумма очков букв дает общее количество очков в слове).

Для этой задачи используется следующая таблица соответствий букв и баллов:

Читать далее →

Продолжаем выполнять домашние задания из Problem set 2 в курсе Computer science CS50 (Harvard). В прошлый раз мы научились шифровать текст сдвигом букв на некое число (ключ), введенный пользователем. А в этот раз решим задачу посложнее, это будет программа Substitution.c и в ней тоже происходит шифрование текста путем замены одних букв на другие по принципу, который вводит пользователь в командной строке при запуске программы. Этот принцип выглядит как строка букв алфавита, расположенных в измененном порядке, так в примере:

$ ./substitution JTREKYAVOGDXPSNCUIZLFBMWHQ
plaintext:  HELLO
ciphertext: VKXXN

Читать далее →

Продолжаем делать домашние задания по курсу Computer science CS50 (Harvard), и в этот раз нужно написать код программы и зашифровать текстовое послание.

Суть задания ceasar.c заключается в том, чтобы программа запрашивала ввод текста пользователя, а затем выводила ниже строку текста в зашифрованном виде с ключом пользователя. Ключ же указывается при запуске программы в командной строке после называния самой программы argv[]. Так в примере запуска готовой программы пользователь вводит ключ = 13 и свой текст «Hello, world!», а на выходе получает этот текст в виде шифра:

Читать далее →

Продолжаем проходить курс Computer Science CS50 (Harvard), и в этот раз будем делать задание на расчет уровня сложности текста по индексу Колман-Лиау (readability.c) на языке программирования C. Согласно идее двух авторов метода, можно оценить сложность текста и таким образом распределить книги по классам школы (от простых текстов, где индекс меньше 1, до академически сложных с индексом более 16). Расчет идет по формуле: 

index = 0.0588 * L - 0.296 * S - 15.8 ,
где L — среднее количество букв на 100 слов в тексте,
 S — среднее количество предложений на 100 слов в тексте. Читать далее →

В курсе cs50 (Гарвард) есть задача по программированию на Си по выявлению правильности номера кредитной карты через алгоритм Луна (credit.c). Разберем эту задачку и покажем два варианта еще решения.

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

Тут-то нам и помогает Алгоритм Луна (создан Гансом Питером Луном из IBM), который позволяет проверить валидность карты таким образом: Читать далее →

Изучая жадные алгоритмы (Greedy Algorithms) на языке программирования C в CS50 (Гарвард), давайте решим задачу про монеты (Cash.c). Допустим, что вам нужно дать сдачу покупателю в магазине и вы хотите свести к минимуму количество монет, которые вы выдаете каждому покупателю.  Если вы кассир, то у вас в кассе есть монеты (25 центов), десять центов (10 центов), пять центов (5 центов) и пенни (1 цент). Как решить, какие монеты и в каком количестве передать покупателю?

Представьте себе «жадного» кассира, который хочет получить как можно больший кусок от этой проблемы с каждой монетой, которую он достает из ящика. Представим, что вы должны покупателю 42 цента, то самая большая первая монета, которую можно взять, — это 25 центов. Этот выбор сократит сумму, которую нужно отдать, до 17 центов, поскольку 42 — 25 = 17. Получается, что при помощи более мелких монет нам нужно будет решить уже более мелкую задачу. Этот подход от наибольшего к наименьшему даст наименьшее возможное количество монет в сдаче.

Решение (Игроглаз): Читать далее →

Любопытная задачка для новичков из CS50 (Гарвард).

Задача: нарисовать пирамидку из игры Марио (mario-less.c) при помощи символов # (решетка или хэш). Пользователя спрашивают: «Из скольких блоков сделать пирамиду?», он вводит число и пирамидка рисуется, с выравниванием по правому краю, вот так:

       #
      ##
     ###
    ####
   #####
  ######
 #######

Решение Игроглаза: Читать далее →

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

#include <stdio.h>

int main (void)
{
int a = -10;
unsigned int b = 5U;
long int c = a + b; // signed + unsigned

printf ("1) (signed int)a -10 will look as unsigned like this: %u\n", a);

printf ("2) (signed)a(-10) + (unsigned)b(5) = %ld\n", c);

return 0;
}

Приоритеты типов:

bool
 char
  unsigned char
   short int
    unsigned short int
     int
      unsigned int
       long int
        unsigned long int
         long long int
          unsigned long long int
           float
            double
             long double