| sport-visoky-7 | Дата: Среда, 09.11.2011, 01:30 | Сообщение # 1 |
Сообщений: 2
Репутация: 0
Статус: Offline
| . Массив целых чисел х[0], x[1], ... x[m+n-1] рассматривается как соединение двух его отрезков:
• начала х[0],...,х[m-1] длины m
• и конца х[m],...,х[m + n -1] длины n.
Не используя дополнительных массивов, переставить начало и конец
Java задача*
|
|
| |
| Freeman | Дата: Среда, 09.11.2011, 02:41 | Сообщение # 2 |
Сообщений: 43
Репутация: 104
Статус: Offline
| Вот процедурка, циклически сдвигающая часть [i0, i1) массива perm[] на s.
В нашем случае, i0=0, i1=m+n, s=n, perm=x.
protected void shift(final int i0, final int i1, int s){
. final int size = i1-i0;
. if( size < 2 ) return;
. s %= size;
. if( s == 0 ) return;
. final int g = CIMath.gcd(s, size);//>0. Это НОД, придётся сделать самому.
. final int t = size/g;
. for(int n=0; n < g; n++){
. . int k = i0+n;
. . int m = perm[ k ];
. . for(int i=1; i < t; i++){
. . . int kk = k-s;
. . . if( kk < i0 ) kk+=size;
. . . if( i1 <= kk ) kk-=size;
. . . perm[ k ] = perm[ kk ];
. . . k=kk;
. . }
. . perm[ k ]=m;
. }
}
|
Страна: Беларусь  |
| |
