質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.34%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

2回答

3484閲覧

数列の循環部分の探索について

turane_gaku

総合スコア8

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2016/09/13 15:45

###前提・実現したいこと
012121234123412341234...という数列の循環部分(1234)の開始と終了のindexを得たい.

###試したこと
フロイドの循環検出法(ウサギとカメのアルゴリズム)で解決できるのではないか,とコードを書いたところ,1212の部分が循環として検出されました.

python

1l = '0121234123412341234' 2 3def f(s, e): 4 a = s 5 b = s 6 7 while True: 8 a += 2 9 b += 1 10 if a >= e: 11 return None 12 if l[a] == l[b]: 13 break 14 15 a = 0 16 while True: 17 a += 1 18 b += 1 19 if b >= e: 20 return None 21 if l[a] == l[b]: 22 break 23 24 return a, b 25 26 27a, b = f(0, len(l)) 28 29print(l) 30for i in range(b): 31 if i == a: 32 print('[', end='') 33 elif i == b - 1: 34 print(']', end='') 35 else: 36 print(' ', end='') 37print()
0121234123412341234 []

どうにかして,1234の部分を検出したいのですが,どうにも上手く出来ません.
どなたかご教授いただけますと幸いです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

1

部分的に繰り返しの箇所を取り出せているのなら、1212までをスキップした残りの文字列に対して同じ事をやればいいのではないでしょうか?

投稿2016/09/13 17:54

swordone

総合スコア20669

efcode👍を押しています

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

  1. 循環部分の長さで判定するか
  2. 循環がN個以上続いたらそれを循環部分と見做すか
  3. 文字列の最後に達するまで判断を続けるか

のいずれかでしょうね。

投稿2016/09/23 08:46

PineMatsu

総合スコア3579

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.34%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問