идеи задач на C для начинающих

[Olej]

Предложение: у кого есть - сформулируйте красивые идеи учебных задач для реализации на C под Linux (в GCC)?
Для начинающих практическое применение студентов.

Потому что всякие "учебные" вопросы (которые очень любят на собеседованиях, тестах) ... типа чему будет равно X+++++Y - это не вопросы, а головоломки, ... заморочки, и не имеют никакого касательства ни к знанию C, ни к методике программирования.

Хорошей задачей я могу считать:
- короткую, простую, не перегруженную деталями задачу ... небольшую
- в которой есть некоторые "подводные камни", необходимость возвращаться к решению по 2-му и 3-му кругу - обычно это обработка ошибок и реакция на неправильный ввод данных пользователем

Например, задача решения "школьного" квадратного уравнения A*X**2 + B*X + C = 0 - очень из этой области ... о чём пишут в знаменитой книжке Моулер и Форсайт, где говорят, что написать хорошую программу решения квадратного уравнения - искусство ... особенно если учитывать возможность плохой численной определённости при некоторых значениях коэффициентов.

Хорошим примером будет итерационное решение нелинейного уравнения f(X) = 0 -- например, бисекцией начального интервала решения [X1 ... X2], но интерес здесь в том, чтобы не задавать произвольную (с потолка) точность завершения итераций, типа EPS=1e-7, а сначала найти её максимально достижимое значение циклом поиска по типу:

Код Выделить Развернуть


double EPS = 1.0;
while( 1. + EPS != 1. ) EPS /= 2.;
EPS *= 2.;
 

Может кто ещё поделится хорошими задачами?

[ihammers]

Собираетесь сделать задачник?

• Перевод из одной системы счисления в другую.
• Найти расстояние между двумя точками (x1,y1; x2,y2).
• Найти сумму всех цифр в 5-значном числе.

[Master_Sergius]

Напиши свой архиватор - вот подумаешь хорошенько

[SeHELLioN]

Перевод из одной системы счисления в другую.

интересно, на первый взгляд не сложно и интересно

Найти расстояние между двумя точками (x1,y1; x2,y2).

на мой взгляд совсем просто

Найти сумму всех цифр в 5-значном числе.

а здесь в чем изюминка?
p.s. ihammers, не критикую, просто данная тема тоже интересна

[ihammers]

Найти сумму всех цифр в 5-значном числе.

а здесь в чем изюминка?
p.s. ihammers, не критикую, просто данная тема тоже интересна

Я бы не сказал что там есть какая-то изюминка. Просто по сравнению с другими языками в C/C++, насколько мне известно, нет специальной функции, которая будет вам выдавать деление без остатка (pascal div/mod). Эта функция просто является лишней. Так как можно просто использовать целочисленное деление и при делении 9/2 у вас будет просто 4, а не 4.5. Если вы хотите получить остаток 0.5, то 9./2 - 9/2.
PS: Возможно это выглядит немного брутально:)
PS:: плюс практика никогда не помешает.

Ниже представлен пример C/C++, который в техзначном числе находит среднее число, сумму чисел и произведение:

Код Выделить Развернуть


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

using namespace std;

int main(void)
{
    int a;
    cout << "Введите трёхзначное число a:";
    cin >> a;

    cout << "a / 10 % 10 = "<< a / 10 % 10 << endl;
    cout << "(a / 100) + (a / 10 % 10) + (a % 10) = "<< (a / 100) + (a / 10 % 10) + (a % 10) << endl;
    cout << "(a / 100) * (a / 10 % 10) * (a % 10) = "<< (a / 100) * (a / 10 % 10) * (a % 10) << endl;

    return 0;
}


[Olej]

Собираетесь сделать задачник?

Нет, не собираюсь
Ко мне часто обращаются ... студенты, выпускники - с вопросами и поднатаскать. И я знаю, что хороших примеров обучению - почти нет.
Если интересно, см. детально другое обсуждение: http://rus-linux.net/forum/viewtopic.php?f=31&t=3301

Найти расстояние между двумя точками (x1,y1; x2,y2).

Это может быть интересно (это и близкие задачи вокруг) только если представлять это в комплексной математике - complex( x1, y1 ) ...
Но это уже я сделал ... тем более, на 15-ти языках программирования : https://debianforum.ru/index.php?topic=7349.0


Сообщение объединено: 27 Март 2014, 12:10:33

Найти сумму всех цифр в 5-значном числе.

а здесь в чем изюминка?
p.s. ihammers, не критикую, просто данная тема тоже интересна

Я бы не сказал что там есть какая-то изюминка. Просто по сравнению с другими языками в C/C++, насколько мне известно, нет специальной функции, которая будет вам выдавать деление без остатка (pascal div/mod). Эта функция просто является лишней. Так как можно просто использовать целочисленное деление и при делении 9/2 у вас будет просто 4, а не 4.5. Если вы хотите получить остаток 0.5, то 9./2 - 9/2.

Ниже представлен пример C/C++, который в техзначном числе находит среднее число, сумму чисел и произведение:

Код Выделить Развернуть


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

using namespace std;

int main(void)
{
    int a;
    cout << "Введите трёхзначное число a:";
    cin >> a;

    cout << "a / 10 % 10 = "<< a / 10 % 10 << endl;
    cout << "(a / 100) + (a / 10 % 10) + (a % 10) = "<< (a / 100) + (a / 10 % 10) + (a % 10) << endl;
    cout << "(a / 100) * (a / 10 % 10) * (a % 10) = "<< (a / 100) * (a / 10 % 10) * (a % 10) << endl;

    return 0;
}


Может быть ... может быть ...
Хотя задача сама, по своему намерению - тупая до безобразия, бессмыслица... Но как упражнение может быть любопытно.

Я, правда, просил на C, а не C++
Потому как а). мы на форуме Linux, б). Linux-у естественен C и противоестественен C++, в). для обучающихся для Linux я бы советовал (только IMHO!) сначала обстоятельно обучиться C, и только потом C++, и C++ после этого идёт чрезвычайно легко
Сообщение объединено: 27 марта 2014, 12:18:49

p.s. ihammers, не критикую, просто данная тема тоже интересна

Если кому интересно ... подбрасываю только лозунги , намётки, штрих-пунктиром:
- всё, что касается рекурсии... и чем проще в формулировке - тем лучше
- например, элементарно: рекурсивный реверс строки (текста) - "12345" -> "54321"
- дальше: рекурсия прямая (головная) и обратная (хвостовая) - одна и та же задача, записанная и так и так

[smallNix]

 Довольно забавные задачки, над которыми стоит поразмышлять (лично по мне) это написать простейшую программу, которая оперирует простейшими числами, например решает квадратное уравнение, но.... так, что бы перед началом решения программа сама выяснила порядок байтов (LE или BE), размеры int'ов и т.д., и только потом выполнила решение.
Кроме того очень интересно писать программки, которые полностью соответствуют POSIX, например SUS4 - это накладывает ограничения на библиотеки, которые можно использовать. По-моему это очень полезно, особенно для студентов. Интересно и полезно посмотреть на задачки, которые должны функционировать в условиях жёстко ограниченных ресурсов, например под Atmega. Если будет время попробую ещё подкинуть.

[Olej]

- всё, что касается рекурсии... и чем проще в формулировке - тем лучше

Из задач на рекурсию одна из самых красивых - это "Ханойская башня":

Код Выделить Развернуть


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

//     ============> 
//    -|-    |     |
//   --|--   |     |
//  ---|---  |     |
//     1     2     3

int nopr = 0;

void put( int from, int to ) {
   printf( "%d => %d,   ", from, to );
   if( 0 == ( ++nopr % 5 ) )
      printf( "\n" );
}

int temp( int from, int to ) {  // промежуточная позиция
   int i = 1;
   for( ; i <= 3; i++ )
      if( i != from && i != to )
         return i;
}

void move( int from, int to, int n ) {
   if( 1 == n ) put( from, to );
   else {
      move( from, temp( from, to ), n - 1 );
      put( from, to );
      move( temp( from, to ), to, n - 1 );
   }
}

int main( int argc, char **argv, char **envp ) {
   int n = 5;                 // число переносимых фишек
   if( argc > 1 && atoi( argv[ 1 ] ) != 0 )
      n = atoi( argv[ 1 ] );   
   printf( "размер пирамиды: n=%d\n", n );
   move( 1, 3, n );           // вот и всё решение!
   if( 0 != ( nopr % 5 ) )
      printf( "\n" );
   printf( "общее число перемещений %d\n", nopr );
   return 0;
}

Вот и всё! Всего то...

Код Выделить Развернуть


bash-4.2$ ./hanoy 2
размер пирамиды: n=2
1 => 2,   1 => 3,   2 => 3,   
общее число перемещений 3

bash-4.2$ ./hanoy 3
размер пирамиды: n=3
1 => 3,   1 => 2,   3 => 2,   1 => 3,   2 => 1,   
2 => 3,   1 => 3,   
общее число перемещений 7

bash-4.2$ ./hanoy 4
размер пирамиды: n=4
1 => 2,   1 => 3,   2 => 3,   1 => 2,   3 => 1,   
3 => 2,   1 => 2,   1 => 3,   2 => 3,   2 => 1,   
3 => 1,   2 => 3,   1 => 2,   1 => 3,   2 => 3,   
общее число перемещений 15

bash-4.2$ ./hanoy 5
размер пирамиды: n=5
1 => 3,   1 => 2,   3 => 2,   1 => 3,   2 => 1,   
2 => 3,   1 => 3,   1 => 2,   3 => 2,   3 => 1,   
2 => 1,   3 => 2,   1 => 3,   1 => 2,   3 => 2,   
1 => 3,   2 => 1,   2 => 3,   1 => 3,   2 => 1,   
3 => 2,   3 => 1,   2 => 1,   2 => 3,   1 => 3,   
1 => 2,   3 => 2,   1 => 3,   2 => 1,   2 => 3,   
1 => 3,   
общее число перемещений 31


А теперь попробуйте то же самое описать без рекурсии! 
Сообщение объединено: 28 марта 2014, 12:25:10

Напиши свой архиватор - вот подумаешь хорошенько

Архиватор - это не интересно
Архиватор - это алгоритмика, патентный поиск ... это к программированию вообще не имеет отношения.

[ihammers]

Собираетесь сделать задачник?

Нет, не собираюсь
Ко мне часто обращаются ... студенты, выпускники - с вопросами и поднатаскать. И я знаю, что хороших примеров обучению - почти нет.
Если интересно, см. детально другое обсуждение: http://rus-linux.net/forum/viewtopic.php?f=31&t=3301

Ясно, как будет время постараюсь ещё подкинуть задачи.

Я, правда, просил на C, а не C++
Потому как а). мы на форуме Linux, б). Linux-у естественен C и противоестественен C++, в). для обучающихся для Linux я бы советовал (только IMHO!) сначала обстоятельно обучиться C, и только потом C++, и C++ после этого идёт чрезвычайно легко

Скажем так, там ничего такого явного на C++ нету, кроме как cout/cin, но их можно заменить.
По пункту а, я считаю странным связывать язык программирования и форум. По поводу пункта б, на чём основывается ваше утверждение, просто очень интересно. На высказывании Linus Torvalds?. По поводу пункта в, может быть, хотя некоторые считают, что лучше разделять эти языки полностью. Я их как-то сильно не разделяю, при работе с OpenCL использую где-то чистый C, а где-то C++, так как не охота тратить время на форматирование вывода.)

[Olej]

Я, правда, просил на C, а не C++
Потому как а). мы на форуме Linux, б). Linux-у естественен C и противоестественен C++, в). для обучающихся для Linux я бы советовал (только IMHO!) сначала обстоятельно обучиться C, и только потом C++, и C++ после этого идёт чрезвычайно легко

Скажем так, там ничего такого явного на C++ нету, кроме как cout/cin, но их можно заменить.

Это понятно...
Я как-то издал такую книгу QNX/UNIX: анатомия параллелизма

Там все примеры кода (а там 40% объёма - примеры) написаны на "C + cout" ... иногда классы по-мелочам появляются.
В отзывах (по сайтам издательств, книготорговцев и т.д.) одни пишут, что "это лушее что написано по параллельностям на русском языке" , а с другой стороны стоит скрежет зубовный "что ж это такое понаписано!". Любо-дорого послушать!

По пункту а, я считаю странным связывать язык программирования и форум. По поводу пункта б, на чём основывается ваше утверждение, просто очень интересно. На высказывании Linus Torvalds?. По поводу пункта в, может быть, хотя некоторые считают, что лучше разделять эти языки полностью. Я их как-то сильно не разделяю, при работе с OpenCL использую где-то чистый C, а где-то C++, так как не охота тратить время на форматирование вывода.)

По п.а) 
- Связан то не язык и форум, а язык и операционная система в которой этот язык применяется. Например, PASCAL в UNIX, в Linux в частности - это совершенно противоестественное сочетание, как корова и седло . Но многие пытаются тянуть PASCAL туда только потому, что они привыкли ... а ещё и жуткие расширения языковые по типу Delphi пытаются притянуть. Это смешно и их же самих жалко: пока они будут PASCAL к UNIX прикручивать, они бы уже 3 языка C освоили за это время.

По п.б) 
- Линус Торвальдс здесь не при чём, он много глупостей говорит ... особенно когда они вдвоём с Э.Таненбаумом соберуться, и вдвоём начинают дурку пороть... 
- UNIX - написан на C,
- C создан только с одной целью - писать UNIX;
- ядро Linux и всё к ядру, модули ядра, драйверы - можно писать исключительно на C;
- утилиты GNU, которые составляют базу утилит UNIX (не только Linux, но и Solaris, Minix, *BSD, QNX, ...) - в большинстве написаны на C;
- свободные открытые проекты, те которые уже привычно стали составной частью Linux, написаны на ... ~60% C, 20% - Perl а последнее время Python, 15% - Java ... и только из оставшихся 5%, может 3-4% проектов написаны на C++ (Qt, wxWidget, ...)
Просто так исторически сложилось. 
В Windows C++ начал использоваться раньше (там нет такого эквивалента как C, сама Windows написана на жутком сочетании соглашений ассемблера + PASCAL + C), и в Windows на C++ гораздо большая относительная часть проектов сделаны. Кроме того он там - популяризируется, вся VisualStudio (до времени .NET) заточена только на C++, и все её описания и примеры.

По п.в) ...
А как их разделить C & C++ ?
Если только 1-2 минимальных конструкции в современном C (ANSI99) можно придумать, постараться таких, которые не будут компилироваться в лоб в C++ ... main() без возвращаемого значения в прототипе и т.п.
И если сам автор Страуструп во всех своих последних книжках обязательно включает главу о совместимости, и использовании средств C в C++.
И если программа C++ скомпилированная и готовая просто не может выполняться при отсутствии C стандартной библиотеки libc.so (по крайней мере так в Linux), эта библиотека для C++ - шлюз ко всем средствам операционной системы Linux, C++ сам не имеет средств взаимодействия с ОС.
В конечном счёте, сам Страуструп и нашёл компромиссное название: C++ является надмножеством C (кстати, первые реализации C++ у Страуструпа и назывались как язык "C с классамси"). А в MacOS - Objective-C++, например ... который изящнее C++ и ближе стоит к C ... так его что, тоже отдельным языком считать? Это уж слишком.
Да и компиляторы (и не один!: GCC, Clang, ...) у них всех единые, и для C, и для C++, и для Objective-C.

[InnaZe]

Сейчас очень популярны контесты. Особенно на олимпиадах среди школьников и студентов. Вот например:
http://acmp.ru/
http://acm.mipt.ru/judge

Там же и хороший архив задач.

[Olej]

Сейчас очень популярны контесты. Особенно на олимпиадах среди школьников и студентов. Вот например:
http://acmp.ru/
http://acm.mipt.ru/judge

Там же и хороший архив задач.

А кто такие контесты?

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

[InnaZe]

А кто такие контесты?

На классических олимпиадах по программированию участникам предлагается некоторый набор задач различного уровня сложности. Решением задачи является программа, написанная на одном из допустимых языков программирования. Эта программа должна корректно считывать любые входные данные указанного формата из определённого входного потока, корректно обрабатывать их согласно условию задачи, и выводить в определённый выходной поток в указанном виде. Для ввода-вывода могут использоваться как стандартные консольные потоки, так и файловые (часто входной файл имеет имя «input.txt», а выходной — «output.txt»).
Все решения проверяются автоматизированной тестирующей системой. Она запускает каждое решение на некотором наборе тестов. После завершения работы программы она оценивает правильность полученных выходных данных.
Особенностью олимпиадных задач является художественность их условия. В условиях редко ведётся речь о структурах данных и алгоритмах, приводящих к решению. Чаще условие задачи представляет собой короткий рассказ со своим сюжетом, героями и конфликтом. Таким образом, чтобы решить олимпиадную задачу, нужно предварительно составить математическую модель событий, и уже по ней подобрать или построить подходящий алгоритм. Алгоритм может быть как одним из уже известных алгоритмов, так и абсолютно новым, непохожим на другие.
Источник:
http://ru.wikipedia.org/wiki/%D0%9E%D0%BB%D0%B8%D0%BC%D0%BF%D0%B8%D0%B0%D0%B4%D1%8B_%D0%BF%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8E

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

В подобных соревнованиях обычно разрешен широкий выбор языков программирования. Никто не запрещает на чистом C писать. Просто слышала от специалистов по подготовке школьников к олимпиадам, что для решения подобных задач, где важна не столько красота кода, сколько скорость его написания, паскаль подходит больше.
Вот еще хорошая подборка:
http://habrahabr.ru/post/128108/

[Olej]

А кто такие контесты?

На классических олимпиадах по программированию участникам предлагается некоторый набор задач различного уровня сложности. Решением задачи является программа, написанная на одном из допустимых языков программирования. Эта программа должна корректно считывать любые входные данные указанного формата из определённого входного потока, корректно обрабатывать их согласно условию задачи, и выводить в определённый выходной поток в указанном виде. Для ввода-вывода могут использоваться как стандартные консольные потоки, так и файловые (часто входной файл имеет имя «input.txt», а выходной — «output.txt»).
Все решения проверяются автоматизированной тестирующей системой. Она запускает каждое решение на некотором наборе тестов. После завершения работы программы она оценивает правильность полученных выходных данных.

Я понимаю, что это условность, "правила игры" ... и в олимпиадных правилах ... приняты такие правила
Но в более свободных условиях, например просто в качестве учебных задач, такие ограничения («input.txt», «output.txt») являются слишком условной рутиной, а ввод-вывод вообще не является интересным предметом обучения.
Часть таких условностей, я так думаю, введено для возможности автоматизированной проверки решений.

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

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

Это (о PASCAL) определённо стереотип ... это можно было (и нужно) утверждать ... лет 25 назад
(я ещё сам читал лекции по PASCAL на "факультете дипломированных инженеров" - повышении квалификации, ещё в 1980 году ... и, думаю, что это был PASCAL-курс первый в СССР ... но на сегодня это - рудимент и ничего больше)
За предложение писать на BASIC - нужно просто убивать (это не моё утверждение, а Э.Дейкстры, классика, который в открытом письме в IEEE предлагал обучающих на BASIC предавать уголовному суду)

Сообщение объединено: 14 Апрель 2014, 16:15:45

Вот еще хорошая подборка:
http://habrahabr.ru/post/128108/

Интересно, посмотрю.


Сообщение объединено: 14 апреля 2014, 16:22:00

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

Удивило, что ранжирование (оценивание) решений ... кто там первый, а кто последний, на одном из показанных вами ресурсов - происходит по размеру (длине) кода решения (числу байт?).
Т.е. формально, если:
- вместо переменной input_number переименовать её в n ...
- или англоязычную строку "input string" заменить на равнозначную русскую "входная строка" (за счёт 2-х байт на символ в UTF-8) ...
... то качество программы (ранг) сразу уменьшится или увеличится.