Нужны задачки

[Taurus727]

Помогите начинающему программировать на Си++ с задачами. Может быть есть ссылки на сборники задач или у вас чего завалялось. Просто учить язык на примерах не реально. Необходима цель. Ее постановка. И решение, соответственно. Разработать логику (алгоритм) решения задачи мне не сложно.Опыт программирования на других языках имею, правда очень сложно перейти с прямых как палка ассемблера с его абсолютными и относительными переходами и бейсика, где goto один из основных операторов на объектно ориентированное программирование где goto вообще считается плохим стилем программирования. Только задачи нужны для консольных приложений - я пока на самом начале и в программирование оконных приложений не лезу иначе утону. В общем дайте задание

[Алексей++]

Taurus727, задание - напиши игру , скажем, тетрис )

[Алексей++]

насчёт goto - я начинал знакомство с языками в таком порядке - сначала бейсик, потом ассемблер, паскаль, си++.

на си++ мне просто ни разу даже в голову не пришло использовать goto - он там просто физически не нужен )  Вот так.

[Taurus727]

Я имел такой же порядок только на паскале почти не писал, так ознакомился чуть. Ну я ведь третий день им занимаюсь (Си++).. Мне простительно. А на счет тетриса - пока до графики не дошел. О тетрисе уже думал

[Алексей++]

Taurus727, а зачем там тебе графикО ? )) Старые добрые букаффки подойдут

[nikedeforest]

Я помню раза два использовал.
А начать можно с крестики нолики, или карточная игра в дурака, при этом минимум графики, а вместо карт обозначения буквенные. А если не игры, то можно реалихзовать метод Гауса для решения СЛАУ, вполне полезно, имхо

[Taurus727]

Мне ближе игры а Гаус... СЛАУ... Сие понятия мне не знакомые думаю "дурак" тут есть о чем задуматься, спасибо. А тетрис алгоритм простой. Я писал на 2 языках в свое время. Пока не знаю как делать вывод в определенной области экрана (консольное приложение). Всякие printf() и cout<< не позволяют координатный вроде как. Как вариант подошло бы просто обновление экрана и начало вывода с верхнего левого угла, так можно координатную систему реализовать самостоятельно. Но пока не понял как делать нечто типа cls - беру лопату и копаю справочник дальше...

[nikedeforest]

Делай как чат.
Очистка экрана cltscr(); библиотеку надо еще подрубить, кажется conio.h, но не уверен.

[Джон]

Я бы предложил такие задания для осваивания ООП. С увеличением сложности

1. Объект типа дробь (операции: ввод, вывод, мат. операции)

2. Строка (операции какие не лень )

3. Графическая фигура (базовый класс) + производные от него - треугольник, линия и тд.

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

[Sla]

не вижу разницу в оконных и консольных приложениях.

Задача - изучить ООП
для оконных приложений
1. принять как аксиому наличие объектов "окна"
2. создать СОБСТВЕННЫЙ объект, с характерными для него свойствами и методами
3 создать потомка

поэтому можно придумывать сколько угодно задач, под любые нужды.

в консольных приложениях проверять работу объекта

[Taurus727]

Для меня разница между консольным и оконным интерфейсом видится так, что когда я создаю консольное приложение я умещаю все в файле ххххх.срр и там ковыряю логику. Изучаю функции самого С++, а когда я делаю проект вин32 то VisualSTUDIO2005 создает мне гору файлов в которых я теряюсь. Ибо пока не разобрался что есть класс и так далее. А ВС генерирует мне по умолчанию все это и я даже пока не могу понять куда и что мне прописывать... Реакции на кнопки и так далее. Вот я и думаю что не зная самих принципов С++ сразу создавать окноное приложение равнозначно неумеющему плавать нырять с яхты //ЗЫ: про очистку консольного окна и позиционирование курсора функция clrscr() в борландовском conio, у меня ВС2005. Такого нет. В интернете накопал рукописные функции для этих целей. Эксперименты продолжаются.

[Serg79]

Кстати, я тоже в свое время тетрис для консоли написал, было прикольно.

[Taurus727]

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

[Sla]

и поневоле пришлось начать изучение 1с блин такая это гадость...

Это жизнь такая

Гадость.... предложи лучшее
и найдутся  люди которые скажут "Гадость"

[Taurus727]

Гадость не потому, что продукт плохой а потому что... Действительно... Почему гадость...

[Sardukar]

в общем тема немного устарела, но если понадобится выкладываю задачи по С С++ Приднестровского Государственного Университета им. Шевченко.

[Dimka]

Зачем сразу тетрисы и прочие аркады, карты? Можно ведь попроще: консольные приложения с потоковым вводом-выводом делать. Диалоговые. Морской бой - типичная игра, в которой картинка н экране не обязательна (юзер может и на листочке нарисовать, а компьютеру картинка вообще не нужна). Чистое программирование с минимумом зависимостей от всяких левых библиотек и графическими мучениями. Ещё разные логические задачки встречаются.

[rumpelstilzchen]

Taurus727, Вот есть очень интересная задача.
Мы имеем кучу камней. Масса каждого камня идивидуальна. Колличество камней - произвольное и меняющееся. Нужно разделить кучу, на две кучи так, чтобы по массе, эти две кучи отличались минимально.

[Алексей++]

это тип "транспортная задача" , если не ошибаюсь )) Решается тупо перебором

[rumpelstilzchen]

ну реши )

[Алексей++]

сейчас решу

[Алексей++]

перебор даже не потребовался )

имеется две пустые кучки.

Код:

//M - номер кучки, с которой работаем, 1 или 2 , переключается по команде "инвертируем".

int M=1;
for(;;)
{
   ищем в оставшихся свободными камнях камень максимальной массы, кладём в кучку M;

   int W1=масса 1 кучки;
   int W2=масса 2 кучки;

   if(M==1)   
  {
    if(W1>W2)
    {
        инвертировать M;
    }
  }
  else
  {
    if(W2>W1)
    {
        инвертировать M;
    }
  }

  if(камни кончились?) break;

}

[rumpelstilzchen]

где гарантия что это самое оптимальное решение? И где гарантия, что другая конфигурация камней, не являеется более приближенной к требуемому решению?

[Finch]

rumpelstilschen, Если по быстрому, то это "жадный алгоритм". По медленому, как сказал Леша, перебор. Кстати, гарантии только страховые компании дают, и то не всегда выполняют.

[Джон]

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

[Алексей++]

где гарантия что это самое оптимальное решение?

своё в студию.

И где гарантия, что другая конфигурация камней, не являеется более приближенной к требуемому решению?

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

[Джон]

Не Лёш, может получится так, что лучше было бы взять 99 маленьких, чем один большой. Поэтому надо стремиться набрать точную половину, это и будет гарантией выполнения условия, в идеале у тебя гарантированно получатся две равные по массе кучки. Если же это в прниципе невозможно, то разница между ними будет минимальной.

[Алексей++]

Джон, в условии задачи - подобрать массу , то есть один параметр, а про количество (второй параметр) не сказано

[Джон]

А где я говорю про количество? У меня тоже один параметр. А количество - это следствие. Ты можешь в одну кучу положить N-1 камней, а во второй останется только N-ый. САмое главное что выборка происходит из всех изначальных камней - этим достигается максимальная точность.

[Алексей++]

Джон, а пока ты будешь подбирать две кучки камней с примерно одинаковой массой - сколько кода при этом выполнится? Мынога. А у меня к этому времени уже будет решение

[rumpelstilzchen]

правильно сказал Finch, что это жадный алгоритм. Скупой платит дважды.
имеем камни (кг) 1, 2, 3, 4. По твоему, алгоритму, получается две кучи 4 (1 и 3) кг и 6 (2 и 4)кг.
Оптимальный вариант -  1 и 4, 2 и 3.
Задача осталась не решенной. Мой вариант есть. Могу выложить. Выложить? Только в псевдокоде.

[Джон]

Лёш, я не подбираю две кучки камней с одинаковой массой. Я НАБИРАЮ из ВСЕХ камней массу равную половине исходной массы. Конечно я сначала её отсортирую. А потом перебеор будет уже оптимирован.

Согласен, что ты сделаешь перебор быстрей. Но вот только будет ли это решением задачи, требованием которой является минимальная разница? Это носит вероятностный характер. Повезёт - да, но в самом общем случае - нет.

[Джон]

Задача осталась не решенной. Мой вариант есть. Могу выложить. Выложить? Только в псевдокоде.

А чем тебе мой не подходит?

[Алексей++]

rumpelstilschen, по моему алгоритму получается:
-------------
1) куча: 1,2,3,4
н1:пусто
н2:пусто

ищем самый тяжелый , это 4

2) куча: 1,2,3
н1: 4
н2:пусто

масса набора 1 больше набора 2, переключаемся на набор 2
ищем самый тяжелый , это 3

3)
куча: 1,2
н1: 4
н2: 3

масса набора 2 НЕ больше набора 1
ищем самый тяжелый , это 2

4)
куча: 1
н1: 4
н2: 3,2

масса набора 2 больше набора 1, переключаемся на набор 1
ищем самый тяжелый , это 1

5)
куча: пусто
н1: 4,1
н2: 3,2

-------------


Джон, нету там никакой вероятности, алгоритм обеспечит точную подгонку, согласись. Или покажи глюк


rumpelstilschen, давай своё решение

[rumpelstilzchen]

Джон: да, решений много и твой работает.

Алексей1153++: у меня просто другой алгоритм. сейчас, найду и покажу

[Алексей++]

это просто клёво, когда есть много решений

[Sla]

В футбол в детстве играли?
Два человека начинают поочередно набирать себе команду
в результате почти одинаковые команды получались

Здесь же можно пойти по другому пути
Тяжелый - легкий

Но! в таком случае количество камней в кучах будет одинаково.

[Sla]

вот например
4 3 1 2
первая куча 4 1
вторая 3 2

но, а если
4 3 1?
первая куча 4
вторая 3 1
моя пошла думать...

[Алексей++]

Слав, всё правильно , и даже если
10,1,1,1,1,1,1

будет

10
1,1,1,1,1,1

всё, сходицо

[rumpelstilzchen]

1. 4 камня, возводим в квадрат. Получаем 16 блоков.
2. в каждом блоке по 2 секции - "кучи"
3. распределяем каждый камень таким образом, чтобы он прошел по каждой куче, каждого блока, но так, чтоб "свзаимодействовал" с каждым камнем, рапределенным таким же способом.
4. в каждом блоке вычитаем из большей кучи, кучу меньшую.
5. получаем результат наименьшего значения по требуемому условию

Плюсы: нейронная сортировка.
Минусы: большой объем задействованных ресурсов, если использовать линейный метод. При оптимизации, ресурсо-требуемость сокращается.

[Алексей++]

1. 4 камня, возводим в квадрат. Получаем 16 блоков.

ага... 100000 камней возводим в квадрат... Таких кампутеров тогда ещё не было

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

а зачем именно так? Тем более, что и непонятно. Если хочется перебрать все варианты сочетаний из N камней - заведи N*2 -разрядное двоичное число, и инкреминируй от 0 и до переполнения (2^(N*2)) .
Отсеивай только те числа, в которых 10 бит.
Интерпретируй так: первые Nбит - маска для первого набора, последние N бит - маска для второго.
Также отсеивай случаи, когда биты в масках пересекаются (то есть когда Mask1 & Mask2 не равно 0)

из подходящих сочетаний выбери те, которые имеют меньшую разницу в суммарной массе. Усё.

Код:

Плюсы: нейронная сортировка.

где тут нейроны?

Код:

Минусы: большой объем задействованных ресурсов, если использовать линейный метод. При оптимизации, ресурсо-требуемость сокращается.

ага, много кода, много озу

[rumpelstilzchen]

>где тут нейроны?

камни

[Алексей++]

это круто. Зачем такая самокритика, не надо

[rumpelstilzchen]

взаимодействие между камнями - нейронные связи.
нейронных связей в мозгу человека - больше чем атомов во вселенной. )

[Алексей++]

ну про атомы во вселенной это ты конечно загнул... Если бы ДАЖЕ каждая связь состояла из одного атома, то этого бы всё равно не получалось бы

нейрон - это запоминающий элемент со связями (камень не катит)

Кстати, ещё можно было бы использовать генетический алгоритм, озу потребуется с понты, но долго вычисляться будет

[rumpelstilzchen]

>генетический алгоритм

это что?

[Sla]

вот...
1 куча -> самый тежелый из остатка
проверка на вес кучи с весом последнего тяжелого камня из остатка
2 куча -> самый тяжелый из остатка или вся оставшаяся куча

4 1 1 1
1. 4
2. 1 1 1

4 3 2
здесь можно ввести еще одно условие на проверку... (отдав предпочтение последнего камня второй куче)
1. 4
2. 3 2

9 8 3 2 1 1 1 1
1. 9 1 3
2. 8 1 2 1 1

[Алексей++]

rumpelstilschen, это алгоритм, где моделируется содранный у природы естественный отбор , вкратце не смогу рассказать - сам никогда не пользовался. Поищи. Штука занятная ) . Там правила некоторые (так же из природы) - каков процент мутации параметров, перекрёстный обмен генами, передача наследственности. Ну и вычисляется это всё долго, конечно

[Алексей++]

Слав, а в моём алгоритме получается
1:9211
2:8311

[Sla]

Алексей1153++, в твоем алгоритме уравнивается команды в правах, предпочтение отдается слабому...

+1

[Алексей++]

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

[rumpelstilzchen]

Алексей1153++, твой алгоритм надо тестировать. а мой не надо.

[Алексей++]

да твой ещё не написан, а мой вовсю работает ) Покажи мне исходные данные, при которых будет косяк?

[rumpelstilzchen]

>Покажи мне исходные данные, при которых будет косяк?

Алексей1153++, говорю, не знаю, тестировать нужно. Сам алгоритм тестировать. Не прогу.

[Sla]

rumpelstilschen, так мы его уже оттестировали
А почему твой тестировать не надо? У тебя что самопроверяющийся алгоритм?
А у Лешки работающий, даже в тяжелых условиях.

[Sla]

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

не, ты отдаешь предпочтение слабой куче...

[Алексей++]

rumpelstilschen , программу я не писал, я на работе, другой программой занят. А алгоритм интуитивный. А давай, напиши программу , если не лень, заодно и проверим ) И RND прикрути для тестов

[rumpelstilzchen]

Sla, мой тестировать не надо, потому что он рассматривает все варианты конфигурации камней, и выбирает тот, который требуется по условию.

Алексей1153++, сейчас нет. я занят. на мне 2 курсовика висят )

[Алексей++]

курсовики, говоришь... А вот программа

Код:

{
	//исходная куча
	const int SourceHeap[]={1,2,3,4,5,6,7,8,9};

	int N=sizeof(SourceHeap)/sizeof(*SourceHeap);

	//рабочая куча
	int* WorkCommonSet=new int[N];
	::memmove(WorkCommonSet,SourceHeap,N*sizeof(*SourceHeap));

	//наборы
	int* Set1=new int[N];
	int* Set2=new int[N];
	::memset(Set1,0,N*sizeof(*Set1));
	::memset(Set2,0,N*sizeof(*Set2));

	//не сортируем WorkCommonSet, будем так искать максимальный
	//элемент, а потом заменять на 0 после использования

	int S=1;//текущая куча
	int W1=0;//вес набора 1
	int W2=0;//...2
	int N1=0;//камней в наборе 1
	int N2=0;//...2

	for(;;)
	{
		//ищем в общей куче максимальный элемент, вес его - maxStoneW
		int maxStoneW=0;
		int* pMax=0;

		int* p=WorkCommonSet;
		for(int i=0;i<N;i++,p++)
		{
			if(*p)
			{
				if(*p > maxStoneW)
				{
					maxStoneW=*p;
					pMax=p;
				}
			}
		}

		//если не найдено ничего - выход
		if(!maxStoneW)break;

		//вытаскиваем камень из общей кучи
		*pMax=0;


		if(S==1)
		{
			//кладём камень в набор 1
			Set1[N1]=maxStoneW;
			N1++;
			W1+=maxStoneW;

			if(W1>W2)
			{
				S=2;
			}

		}
		else
		{
			//кладём камень в набор 2
			Set2[N2]=maxStoneW;
			N2++;
			W2+=maxStoneW;

			if(W2>W1)
			{
				S=1;
			}
		}
	}
//Set1 и Set2 - результат , N1 и N2 - длины массивов
	delete [] WorkCommonSet;
	WorkCommonSet=0;

	delete [] Set1;
	Set1=0;

	delete [] Set2;
	Set2=0;

}

[rumpelstilzchen]

я не провел алгоритм по исходнику. должно получится 2 кучи. 22 кг и 23 кг. получил ехешник? дай посмотреть. и исходник тоже, полностью.

ты удалил указатель           >  delete [] Set1;
а потом его инициализируешь   >  Set1=0;

разве так можно?

[Алексей++]

зачем экзешник, я в дебаге проверил всё )))

1:9 6 5 2 1
2:8 7 4 3

[rumpelstilzchen]

прочитай пожалуйста еще раз, я изменил сообщение

[Алексей++]

исходник полностью перед тобой, просто я в другом проекте временно кусок кода набросал, ибо некогда проект разщводить новый. В дебаге проверил. И ты можешь тоже проверить. Хотя судя по "удалил указатель" - вряд ли сможешь...
Я освободил память, на которую указатель указывает, а указатель обнулил (всегда так делаю - не нарвёшься на unallocated)

[rumpelstilzchen]

как ты можешь освободить память, на которую указатель указывает? Это же "куча". Обнулить ее можно только при перезагрузке. Можно/удалять именно указатели, чтоб они не стали "дикими" или "зависшими". После удаления указателя, область в "куче", остается занятой. Использовать ее повторно нельзя. Это ведь динамическая память. После удаления указателя, когда его уже нет, как ты производишь работу с ним? Компилятор скажет, что я незнаю такую переменную.

[Алексей++]

дикие указатель - это перл Держите меня семеро, а то абасцака....


>как ты можешь освободить память, на которую указатель указывает? Это же "куча".

 -лягко. Именно кучу. А не кучу - можно только обнулить. При чём в любое время, как и не кучу...

А с компилятором я договорился )


меня тЫрзают смутные сомнения

[rumpelstilzchen]

нет, серьезно, это я, наверно, что-то не понимаю

[Алексей++]

rumpelstilschen, это хорошо, что ты это понимаешь (то, что ты что то не понимаешь). Ценю.

Указатель - это переменная, которая хранит адрес начала участка памяти. Конечно, можно и указатель удалить, если он был динамически создан, но у нас он не динамический. А вот память под массив - да. Её я выделил by new, потом освободил by delete [] , а поскольку указатель указывает теперь на мусор = я обнулил на всякий пожарный. А то вдруг я что то напишу дальше , да и возьму поюзаю нехороший адрес?

[rumpelstilzchen]

да, я разобрался, это я перепутал, действительно. извиняюсь.

[rumpelstilzchen]

*.ехе то сделай. проверим.

[Dimka]

rumpelstilschen, это алгоритм, где моделируется содранный у природы естественный отбор , вкратце не смогу рассказать - сам никогда не пользовался. Поищи. Штука занятная ) . Там правила некоторые (так же из природы) - каков процент мутации параметров, перекрёстный обмен генами, передача наследственности. Ну и вычисляется это всё долго, конечно

Как раз целью этих алгоритмов является ускорение поиска решения за счёт применения эвристики по сравнению с полным перебором (когда метод ветвей и границ неприменим).

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

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

[Алексей++]

rumpelstilschen, не буду делать, ты же программист - напиши сам, копировать через буфер обмена умеешь, я полагаю

dimka, вот имено поэтому и не стоит усложнять ))

[rumpelstilzchen]

напишу я мой алгоритм, только позже, сейчас некогда

[Алексей++]

ок

[Sla]

rumpelstilschen, у нас уже здесь был один такой, который некогда... все обещал свою ось написать... и рассказать нам всю правду о видеокартах... Сказал слово - держи.

[rumpelstilzchen]

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

<убил аттач>

[Sla]

rumpelstilschen, и что ты нам рассказал?
перевел карточку в режим 320*200 пикселей, 256 цветов
и все?

да хрен с ними с видеокартами.... та и не такое можно творить... Есть лишний монитор? могу рассказать.

Ты давай нам по теме...
А то есть еще одна незаконченная задача, она в общении лежит, и называется Задача для бегинера....

[rumpelstilzchen]

>Задача для бегинера
Это как "Курс молодого бойца"? И кто такой "БегИнер"? Или "БегинЕр", не знаю как правильно.

>Ты давай нам по теме...
сейчас не могу, нет времени.

>перевел карточку в режим 320*200 пикселей, 256 цветов
и все?
Здрасте. Я дал шаблон проги на асме, как с графикой работать. Изменяй и пиши что хочешь.

[Dimka]

Помнится, была когда-то давно байка, как кто-то с помощью ассемблера пытался выводить пиксел на новейшем и крутейшем адаптере VGA.

[Sla]

rumpelstilschen, не отвлекайся давай реализацию...