共用方式為

Ponder this

  • 發行項

I just discovered this site. It contains all sorts of math/cs/algorithm-related problems. Some of them are beautiful, others so-and-so... But at least in my case, the effects can be already seen - red eyes :-)

Here is an really nice challenge:

Ponder This Challenge: This month's puzzle was sent in by Joe Buhler.
It came from a SIGCSE meeting via Eric Roberts.

A read-only array of length n, with address from 1 to n inclusive,
contains entries from the set {1, 2, ..., n-1}.
By Dirichlet's Pigeon-Hole Principle there are one or more duplicated
entries. Find a linear-time algorithm that prints a duplicated value,
using only "constant extra space". (This space restriction is important;

we have only a fixed number of usable read/write
memory locations, each capable of storing an integer between 1 and n.
The number of such locations is constant, independent of n.
The original array entries can not be altered.) The algorithm should
be easily implementable in any standard programming language.

Or this one:

Ponder This Challenge: A large rectangle is partitioned into smaller rectangles, with sides parallel to those of the large rectangle. Each smaller rectangle has at least one side whose length is an integer. (For some rectangles this may be the horizontal side; for others, the vertical side.)

Prove that the same holds true of the large rectangle.

P.S. - please don't post the solutions in the comments so that others can enjoy the problems!

Comments

  • Anonymous
    May 04, 2004
    Romanians are cool at stuff of this kind! :-) Just "some" romanian names from those who answered correctly: Gheorghe Coserea, Dan Dima, Mihai Cioc, Sorin Ostafiev, Radu Boghirnea, Mihaela Toarta, Cosmin Negruseri, Dan Florescu, Nelu Cioc, Adrian Atanasiu, Cristian Mocanu, Dan Ungureanu, Cosmin Arad, Traian Dajma, Ionel Santa, Marian Olteanu, Marian Vasile, Nicusor Timneanu, Ionut Marius Breaz, Octavian Marasescu, Marcel Isaila, Cristian Stagarescu, Laura Apostoloiu, Melica Antoniu, Ion (John) Munteanu...
  • Anonymous
    July 07, 2004
    Salut,

    Nice problem the first one. I can give u another one that has the same genre of solving:

    You have a simple linked list. Check that the list has a loop in O(n) using finite memory storage...