Задачи для тренировки и лучшего понимания

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:

@Somebody · 20.11.2010, 12:57

Сообщение от ForEveR

Что нужно добавить, чтобы этот код скомпилировался на любом компиляторе, поддерживающем шаблоны?

C++

template<class T>
class Class
{
public:
        virtual ~Class()=T;
        void foo(T a)
        {
        }
};

Мысль читерская, но других нет

Закомментировать его, тогда точно скомпилируется

Если это деструктор, то =0, это чисто синтаксический элемент, значит, бесполезно пытаться сделать каким бы то ни было образом T равным нулю. Если только #define, но тогда вместо <class T> уже будет фигня.

@ForEveR · 20.11.2010, 23:39 **[ТС]**

Somebody, C #define мысль верная. Надо вспомнить об еще одной директиве препроцессора, которая вернет T значение шаблонного типа.

Добавлено через 8 часов 59 минут
Собственно чуть поменяю тот код. Тут он более очевиден что-ли и на любом компиле вызовет ошибки. Задача все та же

C++

#include <iostream>
 
template<class T>
class Class
{
public:
        virtual ~Class()=T;
        void foo(T a)
        {
        }
}; 
 
template<class T>
class Der:public Class<T>
{
public:
    ~Der()
    {
    }
};
 
int main()
{
    Der<int> Ob;
    return 0;
}

Evg · 22.11.2010, 13:06

Задача на понимаение работы с плавающими (float point) числами

Дан исходник. Содержимое функции func неизвестно

C

#include <stdio.h>
 
float
func (void)
{
  /* чёрный ящик */
}
 
int
main (void)
{
  float f1, f2;
  int r1, r2;
 
  f1 = 5.0f;
  f2 = func();
 
  r1 = (f1 > f2);
  r2 = (f1 <= f2);
 
  printf ("r1=%d r2=%d\n", r1, r2);
 
  return 0;
}

Написать содержимое функции func, чтобы при работе теста выдавалась следующая печать:

Код

r1=0 r2=0

@Хохол · 22.11.2010, 15:15

Возможно

return 0.0/0.0.

С телефона, проверить не могу.

@Kastaneda · 22.11.2010, 15:26

Сообщение от Хохол

Возможно return 0.0/0.0. С телефона, проверить не могу.

Ага, а я голову ломал

А почему так?

@Хохол · 22.11.2010, 15:28

Читай про not a number

@Kastaneda · 22.11.2010, 15:39

почитал, можно еще так return pow(-5.0,0.5);

@ForEveR · 01.12.2010, 05:30 **[ТС]**

Таки решите кто-нибудь в посте 922.

Evg · 01.12.2010, 12:50

Сообщение от ForEveR

Таки решите кто-нибудь в посте 922.

Задачи бывают интересные и не интересные. Если все на задачу забили, значит она не интересная

Evg · 02.12.2010, 13:14

Сразу предупреждаю, что задача сложная.

Имеется тест. Тест явился результатом разбора на большой задаче, с ошибкой в которой мы столкнулись на работе. Конструкция __attribute__((noinline)) запрещает компилятору делать подстановку функции (чтобы на оптимизациях там что-нибудь не схлопнулось). Это самый простой способ, чтобы оптимизации гарантированно не убили интересную ситуацию (чтобы не нужно было бы писать более сложные примеры).

C

#include <stdio.h>
 
double d = 5436277361664796672.000000;
long long ll = 5436277361664796253LL;
 
int __attribute__((noinline))
func1 (void)
{
  double d1 = (double)ll;
 
  if (d > d1)
    return 1;
  else
    return 0;
}
 
int __attribute__((noinline))
func2 (void)
{
  if (d > (double)ll)
    return 1;
  else
    return 0;
}
 
int
main (void)
{
  printf ("%d %d\n", func1(), func2());
  return 0;
}

Этот тест я запускал на intel'е и на sparc'е. Использовал gcc в режиме с оптимизациями и без оптимизаций. Получил следующие результаты:

sparc: "gcc" напечатал "0 0"
sparc: "gcc -O2" напечатал "0 0"
intel: "gcc" напечатал "0 1"
intel: "gcc -O2" напечатал "1 1"

Объяснить расхождение. Так или иначе при разборе ситуации полезно было бы иметь возможность повторить всё это самому, но, понятное дело, практически ни у кого нет возможности запустить этот код на sparc'е. Вместо sparc'а можно попробовать запустить под виндой при помощи microsoft'овского или borland'овского комплятора. Я не знаю, какие они выдадут результаты, но в любом случае что-то с чем-то не совпадёт (потому как мы уже видим три разных результата)

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

Подсказка

SPARC'овский gcc работает правильно. Intel'овский gcc косячит и выдаёт неправильный результат (без оптимизаций он ошибается только в одном примере, с оптимизациями - в обоих)

@ForEveR · 02.12.2010, 14:36 **[ТС]**

Evg, Студия сие компилировать не решилась. Не в Си, не в CPP.

@МаксимМВ · 02.12.2010, 15:06

Сообщение от Evg

Этот тест я запускал на intel'е и на sparc'е. Использовал gcc в режиме с оптимизациями и без оптимизаций. Получил следующие результаты:

sparc: "gcc" напечатал "0 0"
sparc: "gcc -O2" напечатал "0 0"
intel: "gcc" напечатал "0 1"
intel: "gcc -O2" напечатал "1 1"

У меня на Linux Ubuntu 10.4.1 LTS, компиль gcc, прога напечатала "0 1"

Evg · 02.12.2010, 15:10

Сообщение от ForEveR

Evg, Студия сие компилировать не решилась. Не в Си, не в CPP.

Потому что __attribute__((noinline)) - это расширение компилятора gcc (забыл про это написать). Можно его удалить, но при этом надо будет смотреть код, чтобы компилятор ничего не выхерил. Хотя может быть ничего опасного компилятор и не выхерит (с виду), но у меня просто привычка страховаться от оптимизаций в коротких тестовых примерах

Добавлено через 1 минуту

Сообщение от МаксимМВ

У меня на Linux Ubuntu 10.4.1 LTS, компиль gcc, прога напечатала "0 1"

Запусти ещё "gcc -O2" (с оптимизациями). Ну и посмотри на программу глазами и прикинь, что на самом деле должно быть

@kazak · 02.12.2010, 15:10

ForEveR, у меня билдер тоже отказался компилировать, пришлось __attribute__((noinline)) убрать. Выдает 0 1.

Evg · 02.12.2010, 15:11

Сообщение от kazak

ForEveR, у меня билдер тоже отказался компилировать, пришлось __attribute__((noinline)) убрать. Выдает 0 1.

А с оптимизациями?

@kazak · 02.12.2010, 16:51

Думается так

Ковыряние дизассемблерного кода и справочника по ассемблеру показало следующее. Код для обоих функций генерируется практически идентичный за некоторым исключением. В обоих случаях ll приводится к вещественному типу и результат помещаеться в регистр сопроцессора. Далее вторая функция использует непосредственно регистр, а первая - преобразованное ll (сохраняет d1) записывает в стек. При этом в 64 бита стека запихивается 80-ти битный регистр сопроцессора, достигается это путем округления числа мантиссы до значения, соответствующего размеру мантиссы приемника. Вот из-за этого округления и объясняется, на мой взгляд, разница в работе этих функций. Только вот может я что-то проглядел или недопонял, но мне кажется intel'ая верся работает правильно, а spark'ая - нет.

Сообщение от Evg

А с оптимизациями?

Вроде тоже самое.

@ForEveR · 02.12.2010, 16:58 **[ТС]**

MS без оптимизаций выдает 0 1

Evg · 02.12.2010, 19:03

to kazak

В общем-то написано всё правильно. Но на самом деле правильно работает sparc'овская версия. Потому что по стандарту в преобразовании int64->float64 должна быть потеря точности. А в коде intel'а при преобразовании int64->float80 потери не происходит. Т.е. intel'овский код работает с более высокой точностью, но это идёт в противоречии со стандартом. Возможно, что это какое-то соглашение для платформы Intel, что допустимо по умолчанию работать таким образом. Наверняка есть какие-то опции, по которым код начинает работать в строгом соответсвии со стандартом (но становится более медленным)

@fasked · 02.12.2010, 21:19

Evg, хм...

Код

fasked@fasked:/data/develop/c> gcc main.c 
fasked@fasked:/data/develop/c> ./a.out
0 0
fasked@fasked:/data/develop/c> gcc main.c -O2
fasked@fasked:/data/develop/c> ./a.out
0 0
fasked@fasked:/data/develop/c> gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib64/gcc/x86_64-suse-linux/4.5/lto-wrapper
Target: x86_64-suse-linux
Configured with: ../configure --prefix=/usr --infodir=/usr/share/info --mandir=/usr/share/man --libdir=/usr/lib64 --libexecdir=/usr/lib64 --enable-languages=c,c++,objc,fortran,obj-c++,java,ada --enable-checking=release --with-gxx-include-dir=/usr/include/c++/4.5 --enable-ssp --disable-libssp --disable-plugin --with-bugurl=http://bugs.opensuse.org/ --with-pkgversion='SUSE Linux' --disable-libgcj --disable-libmudflap --with-slibdir=/lib64 --with-system-zlib --enable-__cxa_atexit --enable-libstdcxx-allocator=new --disable-libstdcxx-pch --enable-version-specific-runtime-libs --program-suffix=-4.5 --enable-linux-futex --without-system-libunwind --enable-gold --with-plugin-ld=/usr/bin/gold --with-arch-32=i586 --with-tune=generic --build=x86_64-suse-linux                                                                                                                                                             
Thread model: posix                                                                                                                                                                    
gcc version 4.5.1 20101116 [gcc-4_5-branch revision 166793] (SUSE Linux)

и да... march=core2

@neske · 02.12.2010, 22:17

Вечер добрый

Ребят, с помощью какого алгоритма решается эта задача?

Дано N камней и их массы Wb ... Wn. Написать программу, которая распределяет камни на две кучи так, чтобы разница между массами куч была минимальной.

Простым перебором, или еще каким-то образом?

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	22.11.2010, 15:15	924
	Возможно return 0.0/0.0. С телефона, проверить не могу. 3

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,113 Записей в блоге: 2
	22.11.2010, 15:26	925
	Сообщение от Хохол Возможно return 0.0/0.0. С телефона, проверить не могу. Ага, а я голову ломал А почему так? 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	22.11.2010, 15:28	926
	Читай про not a number 1

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,113 Записей в блоге: 2
	22.11.2010, 15:39	927
	почитал, можно еще так return pow(-5.0,0.5); 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.12.2010, 05:30 [ТС]	928
	Таки решите кто-нибудь в посте 922. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	01.12.2010, 12:50	929
	Сообщение от ForEveR Таки решите кто-нибудь в посте 922. Задачи бывают интересные и не интересные. Если все на задачу забили, значит она не интересная 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	02.12.2010, 14:36 [ТС]	931
	Evg, Студия сие компилировать не решилась. Не в Си, не в CPP. 0

@МаксимМВ C/C++ 93 / 93 / 18 Регистрация: 01.07.2010 Сообщений: 281
	02.12.2010, 15:06	932
	Сообщение от Evg Этот тест я запускал на intel'е и на sparc'е. Использовал gcc в режиме с оптимизациями и без оптимизаций. Получил следующие результаты: sparc: "gcc" напечатал "0 0" sparc: "gcc -O2" напечатал "0 0" intel: "gcc" напечатал "0 1" intel: "gcc -O2" напечатал "1 1" У меня на Linux Ubuntu 10.4.1 LTS, компиль gcc, прога напечатала "0 1" 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	02.12.2010, 15:10	933
	Сообщение от ForEveR Evg, Студия сие компилировать не решилась. Не в Си, не в CPP. Потому что __attribute__((noinline)) - это расширение компилятора gcc (забыл про это написать). Можно его удалить, но при этом надо будет смотреть код, чтобы компилятор ничего не выхерил. Хотя может быть ничего опасного компилятор и не выхерит (с виду), но у меня просто привычка страховаться от оптимизаций в коротких тестовых примерах Добавлено через 1 минуту Сообщение от МаксимМВ У меня на Linux Ubuntu 10.4.1 LTS, компиль gcc, прога напечатала "0 1" Запусти ещё "gcc -O2" (с оптимизациями). Ну и посмотри на программу глазами и прикинь, что на самом деле должно быть 0

@kazak 3528 / 2686 / 334 Регистрация: 11.03.2009 Сообщений: 6,168
	02.12.2010, 15:10	934
	ForEveR, у меня билдер тоже отказался компилировать, пришлось __attribute__((noinline)) убрать. Выдает 0 1. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	02.12.2010, 15:11	935
	Сообщение от kazak ForEveR, у меня билдер тоже отказался компилировать, пришлось __attribute__((noinline)) убрать. Выдает 0 1. А с оптимизациями? 0

@kazak 3528 / 2686 / 334 Регистрация: 11.03.2009 Сообщений: 6,168
	02.12.2010, 16:51	936
	Думается так Ковыряние дизассемблерного кода и справочника по ассемблеру показало следующее. Код для обоих функций генерируется практически идентичный за некоторым исключением. В обоих случаях ll приводится к вещественному типу и результат помещаеться в регистр сопроцессора. Далее вторая функция использует непосредственно регистр, а первая - преобразованное ll (сохраняет d1) записывает в стек. При этом в 64 бита стека запихивается 80-ти битный регистр сопроцессора, достигается это путем округления числа мантиссы до значения, соответствующего размеру мантиссы приемника. Вот из-за этого округления и объясняется, на мой взгляд, разница в работе этих функций. Только вот может я что-то проглядел или недопонял, но мне кажется intel'ая верся работает правильно, а spark'ая - нет. Сообщение от Evg А с оптимизациями? Вроде тоже самое. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	02.12.2010, 16:58 [ТС]	937
	MS без оптимизаций выдает 0 1 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	02.12.2010, 19:03	938
	to kazak В общем-то написано всё правильно. Но на самом деле правильно работает sparc'овская версия. Потому что по стандарту в преобразовании int64->float64 должна быть потеря точности. А в коде intel'а при преобразовании int64->float80 потери не происходит. Т.е. intel'овский код работает с более высокой точностью, но это идёт в противоречии со стандартом. Возможно, что это какое-то соглашение для платформы Intel, что допустимо по умолчанию работать таким образом. Наверняка есть какие-то опции, по которым код начинает работать в строгом соответсвии со стандартом (но становится более медленным) 2

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	02.12.2010, 22:17	940
	Вечер добрый Ребят, с помощью какого алгоритма решается эта задача? Дано N камней и их массы Wb ... Wn. Написать программу, которая распределяет камни на две кучи так, чтобы разница между массами куч была минимальной. Простым перебором, или еще каким-то образом? 0