malaya_zemlya

Ух тыж-ка, я такое люблю:

1. Деление, есть последовательное вычитание, фперед
int div(int a, int b) {
for( unsigned int aa = abs(a), ab = abs(b), nVal = 0; aa >= ab; ++nVal, aa -= ab );
return nVal * (a > 0 ? 1 : -1) * (b > 0 ? 1 : -1);
}
Можно было сразу вычесть ab-1 из aa и сравнивать с нулем.
2. void line( int x1, int x2, int y ) {
if( y < 0 || y >= h ) return;
if( x1 > x2 ) swap(x1, x2);
x1 = max( 0, x1 ); x2 = min( w - 1, x2 );
for( int i = x1, nPoint = x1 + y * w; i <= x2; ++i , ++nPoint) {
const int nByte = nPoint / 8;
const int nBit = nPoint % 8; (или 8 - nPoint % 8)
screen[nByte] |= 1 << nBit;
}
}
Можно оптимальней написать, вынести деление за цикл, а в цикле прибавлять 1 к биту, если перевалит за байт, то +1 байт и 0 бит.
3.Решение в лоб. Пусть пересекает в некой точке M. Проведем луч AM и пусть он пересекает сторону BC в точке M’. Выпишем уравнения: M лежит на прямой PQ. M лежит на прямой AM’. M’ лежит на прямой BC добавим неравенства, у нас же отрезки, а не прямые. Как-то там преобразуем, думаю оно решится. Но слишком громоздко.

Второй вариант, строим уравнения плоскостей: ABC, PAB, PBC, PAC. Подставляем во все уравнения точки P и Q. Если для ABC знаки разные, а для остальных трех одинаковые, то пересекает.
4. void grip( int *a, int *b ) {
//двигаем B до упора вправо
for( int i = sizeb-1; i >= 0; --i )
b[i+sizea] = b[i];
//сливаем
for( int nA = 0, nB = sizeb, nBMax = sizea + sizeb, i = 0; nA < sizea; ++i )
if( nA >= sizea )
b[i] = b[nB++];
else if( nB >= nBMax )
b[i] = a[nA++];
else if(a[nA] > b[nB])
b[i] = a[nA++];
eles
b[i] = b[nB++];

}
5. a) Ну за NlogN тривиально, думаем как сделать за N. нет ничего другого, как сделать декомпозицию. Разобьем все множества на под-множества (берем нечетную длину, нам так удобней) там по 5 или 7 или ... эллементов. Понаходим медианы во всех маленьких подмножествах. Дальше получим массив медиан. Ничего не остается, как сделать ту же процедуру опять, нам в конце концов нужен один кандидат на медиану, зная его мы потом разобьем первоначальный масив относительно этого кандидата и найдем правильную медиану. Все бы хорошо, но эта рекурсивная процедура поиска кандидата нам даст опять таки log в сложности. Так что я не знаю пока как решить

b) Смысл по идее должен быть тот-же. Просто прйдется разбивать распределенные массивы относительно кандидата в медиану, но по идее это не должно увеличить сложность.

6. Если надо 8, то значит задача сгенерить равномерно распределенные кол-вом кратным 8. Вызываем rand5 два раза, получаем 25 вариантов, надо 24. Решение простое, просто откидываем один любой вариант, какой угодно (в случае его выпадания повторяем процедуру), на решение это не повлияет, rand5 независим от предыдущего значения, так что вызовем мы его два раза или 10 разницы нет. Все бы хорого, но приведенная выше схема не является алгоритмом, надо еше думать.
7. По стандарту unexpected behavior, а в реальности:A, B. Во время вызова конструктора vTable еще не существует, конструктора вызываются снизу вверх.
8. Пишу на мета-языке:
template <class _T, std::string _Name>
class CSingelton {
CSingelton() {}
~ CSingelton() {}
//
class CMutexLock {
public:
CMutexLock() : m_hMutex(CreateMutex(_Name)) {}
void Lock() { … }
private:
HANDLE m_hMutex;
};
public:
static _T& GetObject() {
if( ! m_pInst ) {
CMutexLock Lock;
if( ! m_pInst ) m_pInst = new _T;
}
return * m_pInst;
}
private:
static volatile _T* m_pInst;
};
template <class _T, std::string _Name> volatile typename _T* CSingelton:: m_pInst = NULL;

9. Даже не знаю, что это такое
10. Только фантазирую, ибо далек от этого: округление, специфика представление машинного числа.

Ultras

P.s. а сколько времени давали, я же понимаю это было интевью, то есть отвечать надо было сходу?