Представить линейный массив в виде матрицы

Тема в разделе "WASM.A&O", создана пользователем Rel, 25 янв 2019.

  1. Rel

    Rel Well-Known Member

    Публикаций:
    0
    Регистрация:
    11 дек 2008
    Сообщения:
    2.062
    кароч чет уже подтупливаю... есть задача представить массив чисел любой длины в виде матрицы... то есть формально, зная длину массива L, подобрать для матрицы длину M и ширину N, таким образом, чтобы лишнее число элементов матрицы, получившееся в итоге было минимальным... то есть зная L, подобрать M и N таким образом, чтобы получить M * N минимально большее или равное L (M * N = L)... L, M и N само собой целые числа... если брать M=N=Math.Ceil(Math.Sqrt(L)) получается слишком большой трешхолд для больших чисел (для массива длиной миллион получается примерно 2500 лишних элементов в матрице)...
     
  2. Minzdrav

    Minzdrav Active Member

    Публикаций:
    0
    Регистрация:
    21 мар 2017
    Сообщения:
    996
    Пускай Господь тебе поможет расставить массив, Рель.
     
  3. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    4.189
    Rel, квадрат == самый лучший баланс меж выч. затратами и потерями по памяти.
     
  4. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    413
    M * N = L

    L - либо простое, либо составное.
    Если составное - любая его факторизация дает искомые числа.
    Если простое - ищем ближайшее меньшее не простое.
     
    UbIvItS нравится это.
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    4.189
    впрочем, получив квадрат, можно применить бинарный поиск..

    Код (Text):
    1. int delta=0, m=(input), n=m, tmp=m, threshold=(input);
    2. for tmp > 1 go
    3.      delta=tmp/2;
    4.    if ( m^2 - (m + delta)*(n - delta) > threshold ) tmp =delta;
    5.    else break for;
    6. end for
     
  6. q2e74

    q2e74 Active Member

    Публикаций:
    0
    Регистрация:
    18 окт 2018
    Сообщения:
    259
    в степень возводитьб удобно? :)
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    4.189
    есть лучшие решения == слухаю :)
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    4.189
    а можно совсем забавный метод применить..

    Код (Text):
    1. if (isOdd(L) == true)tmp =L+1;
    2. else tmp=L;
    3. m=2;
    4. n=tmp/2;