Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.06.2008, 00:45
Новичок

Отправить личное сообщение для _asm Посмотреть профиль Найти все сообщения от _asm
 
Регистрация: 31.03.2008
Сообщений: 13

Как оптимизировать алгоритм?
Здравствуйте!
У меня возник следующий вопрос.
Предположим я придумал алгоритм решения какой-либо задачи. Как узнать возможно ли оптимизировать придуманный алгоритм? Если возможно, то как? Может есть какая-нибудь литература по оптимизации? Подскажите пожалуйста.
  #2  
Старый 19.07.2008, 15:01
Новичок

Отправить личное сообщение для _asm Посмотреть профиль Найти все сообщения от _asm
 
Регистрация: 31.03.2008
Сообщений: 13

Неужели никто не знает?
  #3  
Старый 19.07.2008, 20:11
гость

 
Сообщений: n/a

Ну, наверное, тебе стоит для начала изложить суть своего алгоритма.
  #4  
Старый 25.07.2008, 16:26
Новичок

Отправить личное сообщение для _asm Посмотреть профиль Найти все сообщения от _asm
 
Регистрация: 31.03.2008
Сообщений: 13

Пусть, например, нужно разработать алгоритм проверки на правильность судоку. Я сделал следующим образом. Сначала проверяю правильны ли строки:
int ScanUpDown (int A[MaxSizeSudoku][MaxSizeSudoku], int N)
{
int i,j,numb = 0,q = 0,ex = 0;

for (i = 1; i <= N; i++){
for (numb = 1; numb <= N; numb++){
q = 0;
for (j = 1; j <= N; j++){
if (A[i][j] == numb) q = q + 1;
}
if ((q > 1) || (q == 0)){ex = 1; break;}
}
if (ex == 1) break;
}
return ex;
}

Затем проверяю правильность столбцов:
int ScanLeftRight (int A[MaxSizeSudoku][MaxSizeSudoku], int N)
{
int i,j,numb = 0,q = 0,ex = 0;

for (j = 1; j <= N; j++){
for (numb = 1; numb <= N; numb++){
q = 0;
for (i = 1; i <= N; i++){
if (A[i][j] == numb) q = q + 1;
}
if ((q > 1) || (q == 0)){ex = 1; break;}
}
if (ex == 1) break;
}
return ex;
}
Затем малые квадраты:
int ScanSqr (int A[MaxSizeSudoku][MaxSizeSudoku], int N)
{
int quan,t = 0,h = 0,ex = 0,q,i,j,numb;

for (quan = 1; quan <= N * N; quan++){
for (numb = 1; numb <= N * N; numb++){
q = 0;
for (i = (1 + h); i <= (N + h); i++){
for (j = (1 + t); j <= (N + t); j++){
if (A[i][j] == numb) q = q + 1;}
}
if ((q > 1) || (q == 0)){ ex = 1; break; }
}
if (ex == 1){break;}
t = t + N;
if (t == (N*N)){t = 0; h = h + N; }
}
return ex;
}

Программа, использующая эти алгоритмы прошла все 10 тестов. Но я уверен, что можно сделать гораздо проще. Как узнать возможно ли это или нет?

Последний раз редактировалось _asm, 25.07.2008 в 16:28.
  #5  
Старый 26.07.2008, 03:41
гость

 
Сообщений: n/a

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

Вот, например, как я написал чекер для судоку на питоне:
Код:
# coding: utf-8
import math

def check(A):
    n = len(A)

    # проверяем строки
    for row in A:
        if sorted(row) != range(1, n+1): return False

    # проверяем столбцы 
    for j in range(n):
        col = [A[i][j] for i in range(n)];
        if sorted(col) != range(1, n+1): return False

    # проверяем подквадраты
    m = int(math.sqrt(n))
    for x in range(m):
        for y in range(m):
            square = [A[x*m+i][y*m+j] for i in range(m) for j in range(m)]
            if sorted(square) != range(1, n+1): return False
    return True
       
# тест
print check([
    [7,1,9,4,8,2,3,6,5],
    [3,2,4,6,7,5,8,9,1],
    [8,5,6,3,9,1,2,7,4],
    [4,8,2,5,6,3,7,1,9],
    [1,3,5,7,2,9,6,4,8],
    [6,9,7,1,4,8,5,2,3],
    [2,4,3,9,5,7,1,8,6],
    [5,6,8,2,1,4,9,3,7],
    [9,7,1,8,3,6,4,5,2]])  # => True
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
волновой алгоритм, подскажите как оптимизировать для задачи NewRon Реализация, исходники, языки 4 20.05.2009 19:03