0

私はデータ構造クラスに所属しており、インストラクターから提供されたサンプルデータを再現できません。問題は、ユーザーが指定したメンバー数、ステップ間隔、および開始位置に関する古典的なヨセフス問題です。

具体的には、23歳から5カウントオフの99人は、84人を最後の男として残す必要があると言われています。

私が思いついたのは：65です。入力は99人で、5から23の間隔で開始したのではないかと思い、もう一度走りました。これにより、42が生成されました。

私の割り当てソリューションには循環リンクリストが含まれますが、このcコードはすべての場合で同じ出力を生成します。

#include <stdio.h>

int josephus(int n, long k)
{
  if (n == 1)
    return 1;
  else
  /* The position returned by josephus(n - 1, k) is adjusted because the
   *        recursive call josephus(n - 1, k) considers the original position 
   *               k%n + 1 as position 1 */
 return (josephus(n - 1, k) + k-1) % n + 1;
}

int main()
{
int n = 99;
int k = 23;
printf("The chosen place is %d\n", josephus(n, k) + 5);
return 0;
}

再度、感謝します。

4

1 に答える 1

1

LaForeは、カウントオフがステップオーバーしていると考えています。つまり、1から始めて、2で数えると、最初に人4が殺されます。テキストには1つの例が埋め込まれています。これは直感的ではなく、LaForeがこのように数えている唯一の著者のようです。

于 2013-02-22T16:33:37.350 に答える