#include <cs50.h>
#include <stdio.h>
int sigma();
int main(void)
{
printf("Введите положительное целое число: ");
int n = GetInt();
printf("Сумма чисел от 0 до %i = %i\n", n, sigma(n));
}
int sigma(int k) // создаем рекурсивную функцию суммы от 0 до k
{
if (k==0) return 0;
return (k+sigma(k-1));
}
Автор: admin
Бинарный поиск
bool search(int value, int values[], int n)
{
// смотрим кол-во элементов в массиве, если деление на %2 дает остаток 0, значит, четное кол-во
// иначе нечетное. Если четное - делим отсортированный массив на 2, смотрим последний элемент в левой части. Сравниваем с искомым.
// Если нечетное, то вычитаем 1 элемент, делим на 2, смотрим последний элемент в левой части +1.
// search(needle, haystack, size), где 1 - то, что ищем в массиве; 2 - массив; 3 - размер массива
int a = 0; //начало массива
int b = n-1; // конец массива
int m = b-a; // длина выбранной части массива
int centr, levo, pravo, i;
int aa=values[0];
int bb=values[n-1];
if (aa<=value && bb>=value)
{
do
{
float j = m%2; //для определения четного или нечетного
if (j==0) //если нечетное кол-во элементов в массиве
{
centr = (b-a)/2+a;
if (values[centr]>value)
{
b=centr-1;
}
else if ((values[centr]<value))
{
a=centr+1;
}
else return true;
}
else // если четное кол-во элементов в массиве
{
levo = (b-a+1)/2+a-1;
pravo = (b-a+1)/2+a;
if (values[levo]>=value)
{
b=levo;
}
else
{
a=pravo;
}
}
m = b-a;
printf("\na=%i b=%i\n", a, b);
for (i=a;i<=b;i++)
{
printf("%i\n",values[i]);
}
}
while (m!=0);
// запускаем последний этап проверки, т.к. если остался 1 элемент в конце m может быть равным 0 и цикл закончится
if (values[a]==value) return true;
else return false;
} else return false;
}
Линейный поиск
bool search(int value, int values[], int n)
{
// search(needle, haystack, size), где 1 - значение из командой строки, которую ищем в стоге; 2 - массив; 3 - размер массива, номер элемента в массиве
int i;
if (n<=0) return false;
else
{
for (i=0; i<n; i++)
{
if (value == values[i]) return true;
}
}
return false;
}
Пузырьковая сортировка
Реализация метода пузырьковой сортировки (попарное сравнение и смена места в массиве)
void sort(int values[], int n) // sort(haystack, size); - массив + его размер
{
if (n<1) return;
else
{
int i, a, b;
int j=1;
do
{
j=0;
for (i=1; i<n; i++)
{
a = values[i-1];
b = values[i];
if (values[i]<values[i-1])
{
values[i] = a;
values[i-1] = b;
j=1;
}
}
}
while (j!=0);
return;
}
}
Работа с картотекой
p – people – команда, которая спросит номер документа и выведет имя человека, которому он принадлежит;
l – list – команда, которая выведет список всех документов в формате passport «2207 876234» «Василий Гупкин»;
s – shelf – команда, которая спросит номер документа и выведет номер полки, на которой он находится;
a – add – команда, которая добавит новый документ в каталог и в перечень полок, спросив его номер, тип, имя владельца и номер полки, на котором он будет храниться.
documents = [
{"type": "passport", "number": "2207 876234", "name": "Василий Гупкин"},
{"type": "invoice", "number": "11-2", "name": "Геннадий Покемонов"},
{"type": "insurance", "number": "10006", "name": "Аристарх Павлов"}
]
directories = {
'1': ['2207 876234', '11-2'],
'2': ['10006'],
'3': []
}
def people(numbers):
for doc_numbers in documents:
if doc_numbers["number"] == numbers:
print(doc_numbers["name"])
break
else:
print('Такого номера документа нет в базе.')
def people_list():
for persons in documents:
print(persons['type'], '"'+persons['number']+'"', '"'+persons['name']+'"')
def shelf(numbers):
break_marker = False
for shelf_directories in directories.items():
for doc_numbers in shelf_directories[1]:
if doc_numbers == numbers:
print('Данный документ должен лежать на полке', shelf_directories[0])
break_marker = True
break
if break_marker == True:
break
else:
print('Такого номера документа нет в базе.')
def add_command(params_type, number, name, directories_number):
if int(directories_number) == 1 or int(directories_number) == 2 or int(directories_number) == 3:
documents.append({"type": params_type, "number": number, "name": name})
directories[directories_number].append(number)
else:
print('Введенной полки не существует. Запись не осуществлена.')
while True:
command = input('\n \
Введите одну из команд: p, l, s, a, d, m, as. \n \
Для выхода наберите exit. \n \
Для вызов справки наберите help. \n \
Ваша команда: ')
if command == 'p':
people(input('\nВведите номер документа:'))
elif command == 'l':
people_list()
elif command == 's':
shelf(input('\nВведите номер документа:'))
elif command == 'a':
add_command(input('\nВведите тип документа:'), input('Введите номер документа:'), input('Введите имя:'), input('Введите номер полки (1, 2, 3):'))
elif command == 'exit':
break
elif command == 'help':
print('\n \
p – people – команда, которая спросит номер документа и выведет имя человека, которому он принадлежит;\n \
l – list – команда, которая выведет список всех документов в формате passport "2207 876234" "Василий Гупкин";\n \
s – shelf – команда, которая спросит номер документа и выведет номер полки, на которой он находится;\n \
a – add – команда, которая добавит новый документ в каталог и в перечень полок, спросив его номер, тип, имя владельца и номер полки, на котором он будет храниться.')
else:
print('Вы ввели некорректную команду, повторите ввод.')
Функции и условия: практика
Задание: сформировать базу данных и посчитать разные средние и лучшие показатели
students = {'ID01':
{
'name': 'Сергей',
'surname': 'Серов',
'sex': 'мужской',
'experience': False,
'homeworks': {'1': 5, '2': 10, '3': 7, '4': 7, '5': 2},
'exam': 7
},
'ID02':
{
'name': 'Сергей',
'surname': 'Иванилов',
'sex': 'мужской',
'experience': True,
'homeworks': {'1': 6, '2': 10, '3': 9, '4': 8, '5': 5},
'exam': 8
},
'ID03':
{
'name': 'Мария',
'surname': 'Серова',
'sex': 'женский',
'experience': False,
'homeworks': {'1': 5, '2': 10, '3': 7, '4': 7, '5': 2},
'exam': 10
},
'ID04':
{
'name': 'Виктория',
'surname': 'Цинберг',
'sex': 'женский',
'experience':True,
'homeworks': {'1': 8, '2': 10, '3': 7, '4': 6, '5': 8},
'exam': 7
},
'ID05':
{
'name': 'Сергей',
'surname': 'Серов',
'sex': 'мужской',
'experience': False,
'homeworks': {'1': 8, '2': 10, '3': 8, '4': 8, '5': 8},
'exam': 10
},
'ID06':
{
'name': 'Маргарита',
'surname': 'Арутунян',
'sex': 'женский',
'experience': True,
'homeworks': {'1': 8, '2': 10, '3': 8, '4': 8, '5': 8},
'exam': 10
}
}
#расчет средних оценок за домашки и экзамен
def ave_group(homework_or_exam, select_dictonary): #функция принимает форму контроля и словарь (полный или отфильтрованный)
sum_score = 0 #объявляем нулевую сумму баллов
quantity = 0 #объявляем нулевой счетчик количества оценок
if homework_or_exam == '1': # если пользователь ввел 1, то отрабатываем средние оценки за домашние задания
for students_info in select_dictonary.values(): #погружаемся в информацию о студентах
for score in students_info['homeworks'].values(): #погружаемся в словарь с оценками и берем оттуда только оценки
sum_score += score #находим сумму оценок
quantity += 1 #находим количество оценок
average = sum_score/quantity
return average
elif homework_or_exam == '2': # если пользователь ввел 2, то отрабатываем средние оценки за экзамен
for students_info in select_dictonary.values(): #погружаемся в информацию о студентах
sum_score += students_info['exam'] #находим сумму оценок
quantity += 1 #находим количество оценок
average = sum_score/quantity
return average
else:
print('Что-то пошло не так...')
#создаем новый словарь фильтруя по полу и опыту
def dictonary_filter(sex, experience): #создаем новый словарь на основе отфильтрованных данных
# sex - допустимые значения: 0 - все, мужской, женский
# experience - допустимые значения: 0 - все, True - с опытом, False - без опыта
new_dict_students = {}
for id_number, new_dict_info in students.items():
if (sex == 0 or new_dict_info['sex'] == sex) and (experience == 0 or new_dict_info['experience'] == experience):
new_dict_students[id_number] = new_dict_info
return new_dict_students
#поиск лучших
def the_best():
best_list = []
max_score = 0
for best_students in students.values():
sum_score = 0 #начинаем расчет средней оценки за домашние задания
quantity = 0
for score in best_students['homeworks'].values():
sum_score += score
quantity += 1
average = sum_score/quantity
score = 0.6 * average + 0.4 * best_students['exam'] #считаем интегральную оценку
if score > max_score: #если и.оценка > максимальной, то обновляем лист лучших
max_score = score
best_list = [[best_students['name'], best_students['surname'], max_score]]
elif score == max_score: #если и.оценка = максимальной, то добавляем в лист лучших
best_list.append([best_students['name'], best_students['surname'], max_score])
if len(best_list) == 1: #если в списке лучших 1, то выводим одно сообщение
print()
print('Лучший студент: {} с интегральной оценкой {:.2f}'.format(best_list[0][0]+' '+best_list[0][1], max_score))
elif len(best_list) > 1: #если в списке лучших >1, то формируем список из имен и фамилий и запускаем print
name_surname_list = []
for students_in_best_list in best_list:
name_surname_list.append(students_in_best_list[0]+' '+students_in_best_list[1])
print()
print('Лучшие студенты: {} с интегральной оценкой {}'.format(', '.join(name_surname_list), max_score))
else:
print('Что-то пошло не так...')
#главная функция
def main():
while True:
command = input('\n\
1 - вывести среднюю оценку за домашние задания и за экзамен по всем группе\n\
2 - вывести среднеюю оценку за домашние задания и за экзамен по группе в разрезе пола и наличия опыта\n\
3 - определить лучшего студента, у которого будет максимальный балл по формуле 0.6 * его средняя оценка за домашние задания + 0.4 * оценка за экзамен\n\
exit - выход\n\
Введите команду: ')
if command == '1':
print('')
print('Средняя оценка за домашние задания по группе: {:.2f}'.format(ave_group('1', students)))
print('Средняя оценка за экзамен по группе: {:.2f}'.format(ave_group('2', students)))
elif command == '2':
print('')
print('Средняя оценка за домашние задания у мужчин: {:.2f}'.format(ave_group('1', dictonary_filter('мужской', 0))))
print('Средняя оценка за экзамен у мужчин: {:.2f}'.format(ave_group('2', dictonary_filter('мужской', 0))))
print('Средняя оценка за домашние задания у женщин: {:.2f}'.format(ave_group('1', dictonary_filter('женский', 0))))
print('Средняя оценка за экзамен у женщин: {:.2f}'.format(ave_group('2', dictonary_filter('женский', 0))))
print('Средняя оценка за домашние задания у студентов с опытом: {:.2f}'.format(ave_group('1', dictonary_filter(0, True))))
print('Средняя оценка за экзамен у студентов с опытом: {:.2f}'.format(ave_group('2', dictonary_filter(0, True))))
print('Средняя оценка за домашние задания у студентов без опыта: {:.2f}'.format(ave_group('1', dictonary_filter(0, False))))
print('Средняя оценка за экзамен у студентов без опыта: {:.2f}'.format(ave_group('2', dictonary_filter(0, False))))
elif command == '3':
the_best()
elif command == 'exit':
break
else:
print()
print('Вы ввели некорректную команду, повторите ввод.')
main()
Полезные заметки:
- как избавиться от [ ] и опубликовать список через запятую: ‘, ‘.Join(list)
- как опубликовать число с N знаками после запятой: {:.2f}.format(x)
- работа со словарями dict.values() — достаем значений, dict.keys() — достаем ключи, dict.items() — достаем ключи и значения в виде кортежа: (ключ, значение)
Шифр Вижнера
Задача из курса CS50
#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
/*шифр Вижнера*/
//главная функция
int main(int argc, string argv[])
{
// проверка на количество аргументов в командой строке
if (argc != 2)
{
printf("Usage: /home/cs50/pset2/vigenere <keyword>\n");
return 1;
}
// проверка на то, что в шифре одни буквы из алфавита
string word = argv[1];
int a = 0; // счетчик букв в шифре
for (int i=0; i<strlen(word);i++)
{
if (isalpha(word[i]))
{
a=a+1;
}
}
if (a != strlen(word))
{
printf("Keyword must only contain letters A-Z and a-z\n");
return 1;
}
//вводим исходное слово для шифровки
string p = GetString();
int j = 0;
int key = 0;
for (int i = 0, n = strlen(p); i < n; i++)
{
if (isalpha(p[i]))
{
if (islower(p[i]))
{
if (islower(word[j])) key=word[j]-97;
else key = word[j]-65;
int pi = (p[i]-97+key)%26+97;
printf("%c", pi);
}
else
{
if (islower(word[j])) key=word[j]-97;
else key = word[j]-65;
int pi = (p[i]-65+key)%26+65;
printf("%c", pi);
}
j=(j+1)%3;
}
else printf("%c", p[i]);
}
printf("\n");
return 0;
}
Шифр Цезаря
Шифр Цезаря, задача из CS50.
Написать в файле 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).
Программа также должна учитывать, что строчные буквы шифруются строчными, а прописные — прописными.
#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
//главная функция
int main(int argc, string argv[])
{
if (argc != 2)
{
printf("Usage: /home/cs50/pset2/caesar <key>\n");
return 1;
}
else
{
int k = atoi(argv[1]); //конвертируем строку в число
if (k>=0)
{
string p = GetString(); //вводим исходное слово
for (int i = 0, n = strlen(p); i < n; i++)
{
if (isalpha(p[i]))
{
if (islower(p[i]))
{
int pi = (p[i]-97+k%26)%26+97; //сделать так, чтобы при прибавлении ключа пошел по кругу (если pi больше 122, то на второй круг с 97 символа)
printf("%c", pi);
}
else
{
int pi = (p[i]-65+k%26)%26+65; //сделать так, чтобы при прибавлении ключа пошел по кругу (если pi больше 90, то на второй круг с 65 символа)
printf("%c", pi);
}
}
else printf("%c", p[i]);
}
printf("\n");
}
else return 0;
}
}