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

[Trymon]

Это слишком сложно. =(
Но проще всего начинать наоборот. =)

 

[Orshansky]

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



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

Задача элементарная. Ребята, ну я надеюсь вы же не индийские программисты, которым платят за количество строк кода Рефакторинг и оптимизация - это и есть квинтэссенция разработки любого программного обеспечения.

        int y=-1; 
        int x=0; 
        int k=1; 
        int r = razmer*razmer; 

        for(int i=0; i<razmer; k=~k+1) 
        { 
            for(int j=i; j<razmer; ++j)    m[x][y+=k]=r--; 
            for(int j=++i; j<razmer; ++j) m[x+=k][y]=r--; 
        }

я даже удивлен что никто не нашел более простого решения. С каждым годом все меньше и меньше грамотных ребят подсаженых на иглу С#/Java осваивают С/С++, быстрые алгоритмы, ускоряющие структуры данных поэтому приятно видеть вот такие темы, которые к сожалению являются исключением.

#include <stdlib.h>
#include <conio.h>
#include <memory.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 f3(int** m, int razmer)
{
	for (int test=0; test<TEST_ITERATION; test++)
	{
		int y=-1;
		int x=0;
		int k=1;
		int r = razmer*razmer;

		for(int i=0; i<razmer; k=~k+1)
		{
			for(int j=i; j<razmer; ++j)	m[x][y+=k]=r--;
			for(int j=++i; j<razmer; ++j) m[x+=k][y]=r--;
		}
	}
}

// Функция вывода результатов для того, чтобы убедиться в правильности работы моего алгоритма
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("First year Student`s solution time = %d\n", te-ts);
	//show(m, razmer);

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

	
	int** m1=(int**)malloc(razmer*sizeof(int *));
    for(i=0; i<razmer; i++) m1[i] = (int *) malloc(razmer*sizeof(int));

	time(&ts);
	f3(m1, razmer);
	time(&te);
    
	printf("PhD Student`s solution time = %d\n", te-ts);
	//show(m1, razmer);

    getch();
    return 0;
}

Вот результаты моделирования на матрице 257х257

1-й алгоритм - 18-19 секунд.
2-й алгоритм - 15-16 секунд.
3-й алгоритм - 10-11 секунд.

Но следует отметь это еще далеко не предел

 

[Hisp]

Вот еще вариант

 void Fill(int razmer, int[,] m, int TEST_ITERATION)
        {
            for (int test = 0; test < TEST_ITERATION; test++)
            {
                for (int rank = 0; rank < razmer / 2; rank++)
                {
                 
                    {
                        int to = razmer - 1 - rank;
                        int x = (razmer - rank * 2) * (razmer - rank * 2);
                        
                        for (int i = rank; i < to; i++)
                        {
                            m[rank, i] = x--;
                        }
                        for (int i = rank; i < to; i++)
                        {
                            m[i, to] = x--;
                        }
                        for (int i = to; i > rank; i--)
                        {
                            m[to, i] = x--;
                        }
                        for (int i = to; i > rank; i--)
                        {
                            m[i, rank] = x--;
                        }
                    }
                }
                if (razmer % 2 == 1)
                    m[razmer / 2, razmer / 2] = 1;
            }
        }

дюже криво, но работает процентов на 10 быстрее предыдущего.
для матрицы 201, 100000 раз
35.14
30.3

//это на С# под .нетом, сравните хто нить на человеческом языке