Блог пользователя ant.ermilov

Вариации основных функций
Автор ant.ermilov, 14 лет назад, По-русски
После прочтения темы про различные реализации swap-а решил создать ещё одну тему, где можно было бы поделиться кодом.
Есть такая группа простейших подпрограмм, которые приходится писать чаще всего(рекурсивный gcd Евклидом, определение простоты за и т.п.).
Было бы познавательно увидеть чужой код (особенно, если там используется интересный приём) часто используемых функций.

Мои коды:
int gcd(int a,int b)
{
if (a*b==0) (a==0||b==0) return a+b; 
return gcd(b,a%b);
}

bool IsPrime(int x)
{
for (int i=2;i*i<=x;i++) if (x%i==0) return false;
return true;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
В gcd вы переусердствовали с интересными приемами... Что вернет gcd(65536,65536)?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Я вообще всегда пишу так

int gcd(int a, int b){ if(a == 0) return b; else return gcd(b % a, a); }

Предположим, что b больше a. Тогда все корректно.

Если a больше b, то b % a == b и переменные просто свапнутся.


→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я пишу

    int gcd (int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      И на небезызвестном нам сайте так же  ;)

      int gcd (int a, int b) {
	return b ? gcd (b, a % b) : a;
}
      → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится
isprime неверно работает для 1.
можно в конце написать return true; return x!=1
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Я пишу abs(__gcd(a, b))
=)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Но это получается компиляторо-зависимо
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мы тут потестили - оно вообще почти не отличается :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      По скорости, в смысле? Ну в этом ничего удивительного, вряд ли разработчики gcc придумали принципиально новый алгоритм вычисления нода)
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Вот факторизация
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
inline short bit(long long a,short p){//p-й бит
return (a>>p)&1;
}
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
void openf(const string &fname, string mode=""){
string fin=fname+".in";
string fout=fname+".out";
if (mode.size()==1 && mode[0]=='r') freopen(fin.data(), "r", stdin);
if (mode.size()==1 && mode[0]=='w') freopen(fout.data(), "w", stdout);
if (mode.size()==2 ) {
freopen(fin.data(), "r", stdin);
freopen(fout.data(), "w", stdout);
}
}
Вот это висит в шаблоне, для каждой новой задачки на контесте можно быстренько открыть файл:
openf("abababa", "rw"); - будет читаться и записываться в файл
openf("abababa", "r"); - будет только читаться
openf("abababa", "w"); - будет только записываться :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    #define FILENAME "primes"

    int main () {
    freopen(FILENAME".in","r",stdin);
    freopen(FILENAME".out","w",stdout);
    }
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Debug output:

#include <cstdarg>
int eprintf(const char *format, ...) {
  #ifdef DEBUG
  va_list args;
  va_begin(args, format);
  int ret = vfprintf(stderr, format, args);
  va_end(args);
  return ret;
  #else
  return 0;
  #endif
}

...

eprintf("Debug output: %d, %.2lf\n", 123, 4 / 3.0);
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
мне одному кажется, что gcd от двух отрицательных чисел должен быть положительным?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это смотря как определять gcd. Представьте, что вы пишите алгоритм евклида не для чисел а для каких-то элементов с "нормальными" операциями сложения и умножения (видимо это должно быть коммутативным кольцом или что-то типа этого, например многочлены). Тогда там у вас, вообще говоря, нет понятия больше или меньше. gcd можно определить только в терминах делимости. "наибольший" тот, который делится на все остальные. Ну а то что их может быть больше или меньше одного - не страшно :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у нас-то тут НОД двух целых чисел, а не чего-то еще
      а раз в нашем случае НОД -- это число, то оно должно быть наибольшим в смысле сравнения чисел, имхо. Википедия, конечно, не самый авторитетный источник в этом плане, но в ней изложена моя точка зрения:
      Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

      Это конечно не принципиальный вопрос, но тем не менее я с вами не согласен. Нельзя называть НОДом то, что им не является
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Если уж занудствовать, то со строгой математической точки зрения НОД в произвольном евклидовом кольце определен с точностью до умножения на обратимый элемент.
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вопрос про отрицательный НОД возникает у многих, в том числе у самого Кнута :)

        Я тут как-то смотрел видеозапись лекции Степанова (тот что автор STL), так он там упоминал этот случай.
        → Ответить