Помогите пожалуйста с задачей по С

ASokol · 28.05.2009

Пример в студию.

Не будь голословным, пример.

Tempory Mea · 28.05.2009

BFG-9000 сказав(ла):
Эххх, студиозусы. Вот наглядный пример зашоренного мышления, когда изгаляются над префиксно-постфиксными операторами, краткой записью проверки и т.д. вместо кардинального улучшения.
И даже в голову не приходит, как действительно сделать лучше.
Подсказываю - ПРЯМОЕ вычисление значений элементов, а не ерзанье по массиву

Вы занимайтесь сбором в фонд помощи детишкам - у вас это как-то лучше получается, что ли...

PS: Кстати, слово "изголяются" пишется через букву "о"

eyeland · 28.05.2009

Tempory Mea сказав(ла):
Надо так:

Код:

... int size=atoi(argv[1])|1; int* array=new(int[size][size]); ...

да щаз, оператор new в СИ

BFG-9000 · 28.05.2009

Tempory Mea сказав(ла):
Вы занимайтесь сбором в фонд помощи детишкам - у вас это как-то лучше получается, что ли...

Деточка, в отличие от тебя я как минимум написал работающий код и откорректировал вариант ТС-а с указателями. А написанную тобой постную хуйню про оператор new в Сях откомментировали и без меня

Tempory Mea сказав(ла):
PS: Кстати, слово "изголяются" пишется через букву "о"

Специально для тупых морских свинок (которые ни к морю ни к свиньям не имеют отношения

):
Посилання видалено

Значение слова "ИЗГАЛЯТЬСЯ" в толковом словаре Даля
ИЗГАЛЯТЬСЯ - или изгиляться перм. арх. (см. галить) насмехаться, ТРУНИТЬ, зубоскалить, глумиться, подымать насмех; корчить, представлять либо передразнивать кого; ломаться, дурачиться, коверкаться, изгибаться...

До чего же надо быть тупой блондинкой

ASokol · 28.05.2009

BFG-9000, покажи же пример.

BFG-9000 сказав(ла):
Эххх, студиозусы. Вот наглядный пример зашоренного мышления, когда изгаляются над префиксно-постфиксными операторами, краткой записью проверки и т.д. вместо кардинального улучшения.
И даже в голову не приходит, как действительно сделать лучше.
Подсказываю - ПРЯМОЕ вычисление значений элементов, а не ерзанье по массиву

Мое мнение: итераций, как ни крути, будет столько, сколько элементов в массиве (ну может memset еще). Идем дальше, мы знаем, что по спирали значение элементов будут увеличиваться на 1 (инкрементом, который выполняется за один такт процессора); остается только узнавать индекс следующего элемента, закономерность довольно простая:
x - пошли влево
y + вниз
x ++ вправо
y -- вверх
x --- опять таки влево
y +++ опять таки вниз
....

как видно, через каждые два шага количество итераций увеличивается на одну. Итого 81 одна итерация, несколько инкрементов-декрементов, и условные переходы, еще есть проверка с умножением, которое выполняется не за один такт процессора и не за два, которое можно заменить переменной.
Теперь, полумифический алгоритм вычисления значения элемента массива по индексу: полагаю, что там не обойдется без переходов, делений-умножений и прочей лабуды. И эта вся хрень будет выполняться столько же раз как и описанное выше, индексы у тебя опять таки будут вычисляться инкрементами. В итоге по скорости мой алгоритм в разы будет быстрее твоего варианта. Алгоритма ты так и не предложил. В общем, попердел и слился. Думаешь только ты один додумался, что теоретически массив можно заполнять последовательно, вычисляя значение для каждой ячейки?

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

Самое быстрое решение

Код:

#define size 9
int main(int argc, char *argv[])
{
  int array[size][size] = { {81, 80, 79, 78, 77, 76, 75, 74, 73}
                          , {50, 49, 48, 47, 46, 45, 44, 43, 72}
                          , {51, 26, 25, 24, 23, 22, 21, 42, 71}
                          , {52, 27, 10,  9,  8,  7, 20, 41, 70}
                          , {53, 28, 11,  2,  1,  6, 19, 40, 69}
                          , {54, 29, 12,  3,  4,  5, 18, 39, 68}
                          , {55, 30, 13, 14, 15, 16, 17, 38, 67}
                          , {56, 31, 32, 33, 34, 35, 36, 37, 66}
                          , {57, 58, 59, 60, 61, 62, 63, 64, 65} };
  int indexx, indexy; 
  for(indexx = 0; indexx < size; indexx++)
  {
               for(indexy = 0; indexy < size; indexy++)
                          printf("%02d ", array[indexx][indexy]);
               printf("\n");
  }
  system("pause");
  return 0;
}

Тыемураз · 28.05.2009

Итого грандиозный проект под названием "Лечение компьютерного плоскостопия дикими
танцами на платформе 9*9" почти готов.
Остались неразрешенными некоторые нюансы,но это мелочи,по сравнению с разработкой
методики применения такого препарата как "ATOI&NEW".
И все таки есть смысл настаивать на дополнении проекта заданием начальных параметров
движения по спирали в виде начального значения и шага последовательности,который
может бать величиной,изменяемой по определенному закону при переходе от одного витка
к другому.
Например можно представить спиралевидное покрытие магнитных дисков,и тогда матрица
станет основополагающей для файловой системы(это то что мы имеем после форматирования
дисков)
И далее ...

-Alexey- · 28.05.2009

ASokol сказав(ла):

Самое быстрое решение

Код:

#define size 9
int main(int argc, char *argv[])
{
  int array[size][size] = { {81, 80, 79, 78, 77, 76, 75, 74, 73}
                          , {50, 49, 48, 47, 46, 45, 44, 43, 72}
                          , {51, 26, 25, 24, 23, 22, 21, 42, 71}
                          , {52, 27, 10,  9,  8,  7, 20, 41, 70}
                          , {53, 28, 11,  2,  1,  6, 19, 40, 69}
                          , {54, 29, 12,  3,  4,  5, 18, 39, 68}
                          , {55, 30, 13, 14, 15, 16, 17, 38, 67}
                          , {56, 31, 32, 33, 34, 35, 36, 37, 66}
                          , {57, 58, 59, 60, 61, 62, 63, 64, 65} };
  int indexx, indexy; 
  for(indexx = 0; indexx < size; indexx++)
  {
               for(indexy = 0; indexy < size; indexy++)
                          printf("%02d ", array[indexx][indexy]);
               printf("\n");
  }
  system("pause");
  return 0;
}

ASokol · 29.05.2009

Тыемураз сказав(ла):
Итого грандиозный проект под названием "Лечение компьютерного плоскостопия дикими
танцами на платформе 9*9" почти готов.
Остались неразрешенными некоторые нюансы,но это мелочи,по сравнению с разработкой
методики применения такого препарата как "ATOI&NEW".
И все таки есть смысл настаивать на дополнении проекта заданием начальных параметров
движения по спирали в виде начального значения и шага последовательности,который
может бать величиной,изменяемой по определенному закону при переходе от одного витка
к другому.
Например можно представить спиралевидное покрытие магнитных дисков,и тогда матрица
станет основополагающей для файловой системы(это то что мы имеем после форматирования
дисков)
И далее ...

Умный любит учиться, а дурак - учить.

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

BFG-9000 · 29.05.2009

ASokol сказав(ла):
Пример в студию.
Не будь голословным, пример.

ASokol сказав(ла):
BFG-9000, покажи же пример.

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

ASokol сказав(ла):
Мое мнение: ...

Зверски поскипано ибо во мнение постная хуйня и сейчас это будет показано

ASokol сказав(ла):
как видно, через каждые два шага количество итераций увеличивается на одну. Итого 81 одна итерация, несколько инкрементов-декрементов, и условные переходы, еще есть проверка с умножением, которое выполняется не за один такт процессора и не за два, которое можно заменить переменной.

С такими рассуждениями я бы тебе даже метод пузырька не доверил реализовывать

ASokol сказав(ла):
Если есть такой алгоритм и он быстрее моего кода, то показавшему ставлю бутылку коньяка.

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

Итак, тестовый бокс - ноутбук Dell Inspirion 640m, гектар оперативы, проц Т5600.
Среда компиляции - VC6 (да-да, когда мне надо написать консольное приложение в 20 строчек - я юзаю именно ее

)
Ньансы методики сравнения:
1. Память для результирующей матрицы выделяется централизованно, дабы скорость обращения к элементам матрицы была максимально одинакова в обеих алгоритмах и не зависела от распределения памяти. Также память выделяется однократно для обоих алгоритмов и этот процесс во время работы не входит.
2. Сравнение проводится на матрице небольшого объема путем многократных (в примере 100000) повторов алгоритма.
3. Алгоритмы вынесены в отдельные функции. Циклы повтора алгоритмов ВНЕСЕНЫ внутрь этих функций, чтобы избежать 100000 одинаковых в обеих случаях вызовов функций, что может сгладить разницу в работе алгоритмов.

Итак код:

PHP:

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "time.h"

// Кл-во тестовых итераций
#define TEST_ITERATION 100000

// Функция товарища ASokol-а
void f1(int ** array, int razmer)
{
	for (int test=0; test<TEST_ITERATION; test++)
	{
	  int size = razmer;
	  int indexx, indexy;
	  int counter, step, iterator;

		indexx = indexy = (size / 2);
		counter = step = array[indexx][indexy] = 1;   
  
		while (counter <= size * size)
		{
			for (iterator = 0; iterator < step; iterator++)
				array[indexy][step & 1 ? --indexx : ++indexx] = ++counter;
	        if (counter > size * size) break;
		    for (iterator = 0; iterator < step; iterator++)
			    array[step & 1 ? ++indexy : --indexy][indexx] = ++counter;
	        step++;
		}
	}
}


// Моя функция
void f2(int **m, int razmer)
{
	for (int test=0; test<TEST_ITERATION; test++)
	{
		int cnt;
		int i,j, k;

		int lt=1, rb=1, lb=1, rt=1;
		int nextlevellt = 8, nextlevelrb = 4, nextlevellb = 2, nextlevelrt = 6, rp2 = razmer>>1;
		m[rp2][rp2] = 1; cnt = razmer - rp2 - 1;

		for (i=rp2-1; i>=0; i--)
		{
			lt += nextlevellt; 
			rb += nextlevelrb; 
			nextlevellt += 8; 
			nextlevelrb += 8;

			rt += nextlevelrt; 
			lb += nextlevellb; 
			nextlevelrt += 8; 
			nextlevellb += 8;
			m[i][i] = lt; 
			m[++cnt][i] = lb; 
			m[cnt][cnt] = rb;
			m[i][cnt] = rt;

			for (j=i+1, k=1; j<cnt; j++, k++)
			{
				m[i][j] = lt - k;
				m[cnt][razmer-j-1] = rb - k;
				m[razmer-j-1][i] = lb - k; 		
				m[j][cnt] = rt - k; 		
			}
		}
	}
}


// Функция вывода результатов для того, чтобы убедиться в правильности работы моего алгоритма
void show(int **m, int razmer)
{
	for (int i=0; i<razmer; i++)
	{
		for (int j=0; j<razmer; j++) printf("%3d ", m[i][j]);
		printf("\n");
	}
	printf("\n");
}

int main()
{
    int razmer;
	int** m;
	int i;

//	clrscr();
	printf("Vvedite razmer:");
	scanf("%d", &razmer);
	
	m=(int**)malloc(razmer*sizeof(int *));
	for(i=0; i<razmer; i++) m[i] = (int *) malloc(razmer*sizeof(int));

	time_t ts, te;  

	time(&ts);
	f1(m, razmer);
	time(&te);
	printf("Student`s solution time = %d\n", te-ts);

	time(&ts);
	f2(m, razmer);
	time(&te);
	// Раскомментировать для проверки правильности работы моего алгоритма.
	// Рекомендуется TEST_ITERATION приравнять к единице дабы не ждать сотню тысяч проходов
	// show(m, razmer);
	printf("Normal solution time = %d\n", te-ts);

	getch();
	return 0;
}

Результаты тестовых прогонов на матрице размером 501х501:
Мой алгоритм: среднее время 74-76 секунд.
Алгоритм оппонента: среднее время 112-113 секунд.

Итого мой алгоритм работает как минимум на 30 процентов быстрее. что явно находится за пределами возможных ошибок и погрешностей измерения времени работы алгоритма.

Прошу моего оппонента обратить внимание, что несмотря на его жуткие пророчества в моем алгоритме не используется ни одной проверки и ни одной операции умножения/деления за исключением одного сдвига вправо один раз

eyeland · 29.05.2009

Тыемураз сказав(ла):
методики применения такого препарата как "ATOI&NEW"

а что не так с atoi?

ASokol · 29.05.2009

Итого мой алгоритм работает как минимум на 30 процентов быстрее. что явно находится за пределами возможных ошибок и погрешностей измерения времени работы алгоритма.

Разобрал код, алгоритм на порядок быстрее. Хоть это и не заявляемое

ПРЯМОЕ вычисление

, но алгоритм хороший. Спасибо за пример. Осталось решить вопрос с коньяком. Дай номер телефона или аськи, чтобы я с тобой связался.

BFG-9000 · 29.05.2009

ASokol сказав(ла):
Разобрал код, алгоритм на порядок быстрее. Хоть это и не заявляемое , но алгоритм хороший. Спасибо за пример. Осталось решить вопрос с коньяком. Дай номер телефона или аськи, чтобы я с тобой связался.

Это вариант, основанный на том, то в пределах каждой четверти (если разделить матрицу диагоналями) результат представляет собой убывающие столбцы. Ну и правиле, что каждое следующее кольцо элементов от центра к краю на 8 элементов больше предыдущего.
Есть еще вариант, основанный на законах симметрии - можно рассчитатть верхнюю часть матрицы напрямую - аналогично как в текущей версии, а остальные рассчитать на законах симметрии относительно диагоналей. Можешь попробовать

Ну а номер телефона и аськи легко найти тут: https://www.kharkovforum.com/showthread.php?t=417013

Вообще я начинал изучать информатику тогда, когда посидеть за персоналкой (типа Атари) 30 минут в неделю было счастьем. И люди действительно писали алгоритмы, а не собирали кубик рубика из ниибической библиотеки классов

Кто еще помнит такую штуку: Посилання видалено ? А мы на нем писали алгоритмы на республиканских и всесоюзных олимпиадах... Именно алгоритмы, а не изыски на тему "кто короче запишет выражение в терминах какого-то языка"

ASokol · 29.05.2009

Кто еще помнит такую штуку: Посилання видалено ?

В школе маялся такой штукой

Тыемураз · 29.05.2009

Поступило предложение сдать кровь(кстати очень благотворно влияет на организм и его
возможности,помимо того,что приносит еще пользу другому),выпить коньячок и продолжить
проект.
И так мы имеем матрицу,определяющую нашу дорожку-змеевик,разбитую по секторам,скажем
в 4 КБ(плотность записи одинакова по всему участку),каждый сектор соответствует номеру
в таблице,если кластер запорчен,то его номер будет пропущен.
Каждая ячейка матрицы имеет структуру:номер сектора-1Б,номер следующего-1Б.
Для формирования ФС нам необходимо определить поле каталога,поле дескрипторной таблицы
или таблицы индексов и собственно поле данных.Это традиционный подход,но можно идти иным
путем,тут поле деятельности неограничено.Важно бастро находить нужный набор данных,
довести до минимума процессы фрагментации,умело разместить атрибуты.
В силу своих серьезных намерений готов возглавить проект.На этапе проектирования и внед-
рения обеспечу ежедневные 3 бутерброда на основе отборной докторской колбасы и по 30
минут развлечений,сопровождаемых диким танцем блондинки (в проект не хочется брать,больно
уж придирчивы к простым операторам).

Klez · 30.05.2009

Тыемураз сказав(ла):
Поступило предложение сдать кровь
И так мы имеем матрицу,определяющую нашу дорожку-змеевик,разбитую по секторам,скажем
в 4 КБ(плотность записи одинакова по всему участку)

Скажите, это случайно не ваш рассказ?

Посилання видалено

Тыемураз · 30.05.2009

Как все таки хорошо.

Klez · 30.05.2009

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

похоже что вышеприведенная аудиозапись содержит именно ваш рассказ

ASokol · 31.05.2009

Да уж. Интересно про какую ОС и ФС он так глаголит.

Тыемураз · 31.05.2009

Во как.

BFG-9000 · 25.09.2009

ASokol сказав(ла):
BFG-9000, покажи же пример.
...........
Если есть такой алгоритм и он быстрее моего кода, то показавшему ставлю бутылку коньяка.

ASokol сказав(ла):
Разобрал код, алгоритм на порядок быстрее. Хоть это и не заявляемое , но алгоритм хороший. Спасибо за пример. Осталось решить вопрос с коньяком. Дай номер телефона или аськи, чтобы я с тобой связался.

Свидетельствую о том, что товарищ ASokol благородно и честно выполнил свои обязательства проигравшей стороны в вышеописанном споре.