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

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 25 мар 2014, 10:38

Предложение: у кого есть - сформулируйте красивые идеи учебных задач для реализации на 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.;
Может кто ещё поделится хорошими задачами?

Аватара пользователя
Виктория
Писатель
Сообщения: 113
Зарегистрирован: 28 дек 2012, 14:05
Откуда: Самара
Контактная информация:

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

Непрочитанное сообщение Виктория » 26 мар 2014, 14:31

Olej писал(а):Предложение: у кого есть - сформулируйте красивые идеи учебных задач для реализации на C под Linux (в GCC)?
Olej, но у Вас же уже есть такие задачи - Язык Си в Linux: вопросы начального уровня, целых 7 страниц!

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 26 мар 2014, 22:02

Виктория писал(а):
Olej писал(а):Предложение: у кого есть - сформулируйте красивые идеи учебных задач для реализации на C под Linux (в GCC)?
Olej, но у Вас же уже есть такие задачи - Язык Си в Linux: вопросы начального уровня, целых 7 страниц!
Там есть ... отдельные таки задачи ... или даже только намёки, из которых можно слепить такие задачи.
Я оттуда тоже надёргаю... ;-)
И там, скорее, "упражнения" - очень маленькие задачки, на 2 часа работы.
А здесь я имел бы в виду задачи, которые можно и 2-3 дня делать (улучшать) и неделю... То же решение нелинейного уравнения бисекцией - там улучшай и улучшай ;-) .

P.S. Эта тема тоже не из досужего любопытства возникла: меня в порядке ... соседской помощи ;-) попросил свежий выпускник ВУЗа. Вот я ему и выдумываю: а). так чтоб сильно не напрягаясь + б). в свободное от основной работы время. :lol:

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 27 мар 2014, 21:47

Виктория писал(а):
Olej писал(а):Предложение: у кого есть - сформулируйте красивые идеи учебных задач для реализации на C под Linux (в GCC)?
Olej, но у Вас же уже есть такие задачи - Язык Си в Linux: вопросы начального уровня, целых 7 страниц!
Из хороших задач я могу выделить там только несколько:

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

Код: Выделить всё

#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;
   return 0;                    // ошибка
}

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$ gcc -Wall -lm -O -DGCC hanoy.c -o hanoy

Код: Выделить всё

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

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 28 мар 2014, 10:19

Olej писал(а):Может кто ещё поделится хорошими задачами?
Целым "разделом" "хороших" задач будут всё, что касается рекурсии.
P.S. Меня удивляет ... просто поражает, что нынешние студенты просто подступиться не могут к рекурсии (не учат!).
Ну и как же вы хотите потом чтобы они разбирались с функциональным программированием, функциями высших порядков ... с Python тем же.

Пример реверса содержимого строки - прямой циклический реверс + рекурсивный, примр надуманный, но техника выполнения - демонстрирует, и очень понятно:

Код: Выделить всё

#include <stdio.h>
#include <string.h>

// реверс содержимого строки

void revpart1( char* ss, int nn ) {
   int i; 
   for( i = 0; i < nn; i++, nn-- ) {
      char z = ss[ i ];
      ss[ i ] = ss[ nn - 1 ];
      ss[ nn - 1 ] = z;
   }
}
void revers1( char* ss ) { revpart1( ss, strlen( ss ) ); }

void revpart2( char* ss, int nn ) {
   if( 1 == nn ) return;
   if( nn >= 2 ) {
      char z = *ss;
      ss[ 0 ] = ss[ nn - 1 ]; 
      ss[ nn - 1 ] = z;
      if( 2 == nn ) return;
      revpart2( ss + 1, nn - 2 );
   }
}
void revers2( char* ss ) { revpart2( ss, strlen( ss ) ); }

int main( void ) {
   void ( *funcs[] )( char* ) = {                    // варианты выполняющей функции
      revers1, revers2,
   };
   char* datas[] = {
      "123456", "12345", "0123456789 abcdef ghijklm" // варианты тестовых данных
   };
   int j, i;
   for( j = 0; j < sizeof( funcs ) / sizeof( funcs[ 0 ] ); j++ ) 
      for( i = 0; i < sizeof( datas ) / sizeof( datas[ 0 ] ); i++ ) {
         char res[ 80 ];
         ( funcs[ j ] )( strcpy( res, datas[ i ] ) );
         printf( "%s => %s\n", datas[ i ], res );   
      }
   return 0;
}

Код: Выделить всё

bash-4.2$ ./revers 
123456 => 654321
12345 => 54321
0123456789 abcdef ghijklm => mlkjihg fedcba 9876543210
123456 => 654321
12345 => 54321
0123456789 abcdef ghijklm => mlkjihg fedcba 9876543210
Этот пример жутко :lol: показательный относительно русскоязычных UTF-8 строк ... задайте ему русскую текстовую строку! :lol:

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 28 мар 2014, 12:14

Olej писал(а): Из хороших задач я могу выделить там только несколько:
Факториал ... :lol: Ну что ещё можно сказать хорошего про факториал? ... если ним студентам плешь проели ещё с подготовительного отделения...

Можно:

Код: Выделить всё

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

unsigned long long fact1( int n ) {
   unsigned long long f = 1;
   int i;
   for( i = 1; i <= n; i++ ) f *= i;
   return f;
}

unsigned long long fact2( int n ) {     // параметр по значению
   unsigned long long f = 1;
   while( n > 1 ) f *= n--;
   return f;
}

unsigned long long fact3( int n ) {     // хвостовая рекурсия
   return 0 == n || 1 == n ? 1 : n * fact3( n - 1 );
}

unsigned long long fact4( int n ) {     // головная рекурсия
   if( 0 == n || 1 == n ) return 1;
   unsigned long long prev = fact4( n - 1 );   
   return n * prev;
}

int main( int argc, char **argv, char **envp ) {
   int n, m, i;
   unsigned long long ( *funcs[] )( int ) = { 
      fact1, fact2, fact3, fact4,
   };
   while( 1 ) {
      printf( "число: " );
      fflush( stdout );
      m = scanf( "%d", &n );
      if( m <= 0 ) {
         printf( "\n" );      
         break;
      }
      printf( "%d! => ", n );
      for( i = 0; i < sizeof( funcs ) / sizeof( funcs[ 0 ] ); i++ ) 
         printf( "%llu ,  ", funcs[ i ]( n ) ); 
      printf( "\n" );      
   }
   return 0;
}
Вот вам 4 факториала:

Код: Выделить всё

bash-4.2$ ./factorial 
число: 10
10! => 3628800 ,  3628800 ,  3628800 ,  3628800 ,  
число: ^C
1-й - простейший цикл - эталон для сравнения с остальными ...

2-й - напоминание, что параметры в функции передаются по значению, копией (все и всегда! даже массивы ;-) ) ... так можно делать всегда, и не использовать никакие промежуточные переменные ... но не делают - это (передача по значению) вообще предмет отдельного долгого разговора ;-)

3-й - это "школьная" рекурсия ...

4-й - а это другая рекурсия ... в чём разница?
В том, что в п.3 - хвостовая рекурсия: рекусивный вызов последнее действие функции, а в п.4 - это промежуточный результат. Разница в том, что хвостовая рекурсия подлежит формальной оптимизации, котрая может быть сделана компилятором-интерпретатором, а промежуточная - нет.

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

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 09 апр 2014, 21:41

Подсказали мне парочку "олимпиадных" ресурса с большим набором сформулированных задач + там же показаны решения, часто по несколько, альтернативных:

1. Школа программиста

2. El Judge
Online соревнование по программированию в МФТИ
И там и там есть очень любопытные ... смешные задачи, особенно те, у которых указана близко к максимальной "сложность" ... например (сложность )
0011 Зайчик
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
Любознательные могут поупражняться...
И сравнить с лучшими результатами, которые достигли присылавшие решение пыонэры ;-)
В качестве критерия ранжирования лучших попыток служит размер кода закачиваемой программы. При подсчете размера кода не учитываются пробелы, а так же символы переноса и табуляции.

Лучшее решение там показанное:
216
... наверное байт?

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 13 апр 2014, 12:46

Olej писал(а): И там и там есть очень любопытные ... смешные задачи, особенно те, у которых указана близко к максимальной "сложность" ... например (сложность )
0011 Зайчик
Развлекаюсь когда скучно ;-) :

Код: Выделить всё

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

int k;

int howmany( int n ) {
   int i, s = 0;
   for( i = 1; i <= k; i++ ) {
      if( i > n ) continue;
      if( i == n ) s++;
      else s += howmany( n - i );
   }
   return s;
}

int main( int argc, char **argv ) {
   k = atoi( argv[ 2 ] );
   printf( "%d\n", howmany( atoi( argv[ 1 ] ) ) );
}

Код: Выделить всё

bash-4.2$ ./bunny 3 1
1
bash-4.2$ ./bunny 4 3
7
bash-4.2$ ./bunny 7 2
21
bash-4.2$ ./bunny 10 3
274

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 13 апр 2014, 15:06

Olej писал(а): Развлекаюсь когда скучно ;-) :
Неподвижные точки
Перестановкой P[1..n] размера n называется набор чисел от 1 до n, расположенных в определенном порядке. При этом в нем должно присутствовать ровно один раз каждое из этих чисел. Примером перестановок являются 1,3,4,5,2 (для n=5) и 3,2,1 (для n=3), а, например, 1,2,3,4,5,1 перестановкой не является, так как число 1 встречается два раза.

Число i называется неподвижной точкой для перестановки P, если P = i. Например, в перестановке 1,3,4,2,5 ровно две неподвижных точки: 1 и 5, а перестановка 4,3,2,1 не имеет неподвижных точек.

Даны два числа: n и k. Найдите количество перестановок размера n с ровно k неподвижными точками.

Код: Выделить всё

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


int test( int val, int *a, int pos ) { // проверка повторяемости
   int j;
   if( 0 == pos ) return 1;
   for( j = 0; j < pos; j++ )
      if( a[ j ] == val ) return 0;
   return 1;
}

int n, k;

long permutation( int *a, int pos, int np0 ) {
   int i, s = 0;
   for( i = 1; i <= n; i++ ) {
      if( !test( i, a, pos ) ) continue;
      a[ pos ] = i;
      int np1 = np0 + ( pos == i - 1 ? 1 : 0 );
      if( pos == n - 1 ) s += ( np1 == k ? 1 : 0 );
      else s += permutation( a, pos + 1, np1 );
   }
   return s;
}

int main( int argc, char **argv ) {
   n = atoi( argv[ 1 ] );
   k = atoi( argv[ 2 ] );
   int* a = calloc( n, sizeof( int ) );
   printf( "%ld\n", permutation( a, 0, 0 ) );
}

Код: Выделить всё

bash-4.2$ ./stationary 5 2
20
bash-4.2$ ./stationary 9 6
168
bash-4.2$ ./stationary 2 1
0
bash-4.2$ ./stationary 9 0
133496

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

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

Непрочитанное сообщение Olej » 14 апр 2014, 15:43

Вот подсказали ещё ресурс-указатель: Спортивное программирование: «С чего начать?»

Как по мне, то сам термин "спортивное программирование" - это какой-то бред :-o ...
Но как указатель интересных, нетривиальных задач страничка хорошая.

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 7 гостей