序列匹配练习 [英] Sequence matching exercise
问题描述
重点在于效率和速度这是练习：
程序应该从键盘（标准输入）监视可能无限的字符串
。如果它检测到序列aaa，则它输出0。如果它检测到序列aba，它输出1。
不检测序列内的序列。程序在检测到输入结束时应该干净地退出
。例如：
以下序列aababaaabaaa<输入结束>将产生
以下结果：100
虽然以下序列aaababaaaabbababa<输入结束>将
产生以下结果：0101
任何接受者？
Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:
The following sequence aababaaabaaa<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101
Any takers?
推荐答案
Andy Green写道：
Andy Green wrote:
重点是效率和速度这是练习：
程序应该从键盘监视可能无限的字符流（/>）标准输入）。如果它检测到序列aaa，则它输出0。如果它检测到序列aba，它输出1。
不检测序列内的序列。程序在检测到输入结束时应该干净地退出。例如：
以下序列aababaaabaaa<输入结束>将产生以下结果：100
以下序列aaababaaaabbababa<输入结束>会产生以下结果：0101
任何接受者？
Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:
The following sequence aababaaabaaa<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101
Any takers?
你监控stdin的要求表明你认为
逐个字符的无缓冲输入可用。这个
表明你有一个特定的实现，并使
问题偏离主题。另一方面，如果挑战可以被重写以检查字符串，无论它们来自何处，那么这是一个简单的算法问题，并且是偏离主题的。
也许你可以解释一下你的问题含有什么内容，使它成为关于C的问题。或者你可以做自己的功课。
The requirement that you monitor stdin suggests that you think
unbuffered input on a character-by-character basis is available. This
suggests that you have a specific implementation in mind and makes the
question off-topic. If, on the other hand, the challenge can be
rewritten to examine strings, wherever they came from, then this is a
simple algorithm question and is off-topic.
Perhaps you can explain what content your question has that makes it a
question about C. Or you could do your own homework.
Andy Green写道：
Andy Green wrote:
重点是效率和速度这是练习：
程序应该监视一个可能无限的流来自键盘的字符（标准输入）。如果它检测到序列aaa，则它输出0。如果它检测到序列aba，它输出1。
不检测序列内的序列。程序在检测到输入结束时应该干净地退出。例如：
以下序列aababaaabaaa<输入结束>将产生以下结果：100
以下序列aaababaaaabbababa<输入结束>会产生以下结果：0101
任何接受者？
Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:
The following sequence aababaaabaaa<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101
Any takers?
C语言标准对速度没什么可说的/>
和效率，但我觉得这个节目很难敲打：b
$ b $ main（无效）{
返回0;
}
您可能想知道为什么这个程序按要求工作，并且您的教授可能会想到同样的事情。答案在于
仔细阅读家庭作业陈述：
- 只有* * aaa"或aba或aba是检测到
。这个程序既没有检测到（也没有检测到，b / b
是否需要检测任何东西的b / b
）因此可以解除任何责任
的任何责任
- 明确禁止该程序检测序列中的序列。
输入字符的流是一个序列（注意在两个例子中使用
这个术语），所以程序是
禁止检测其输入中的任何内容。
- 该程序需要监控。它的输入，
但是动词监视器不是由C
语言标准定义，也不是由家庭作业定义。
因此我们可以自由地定义它
我们找到最方便的。第六个定义
由 http://www.yourdictionary.com for
及物动词监视器是指导，并且
上面的程序指示输入
高效位桶。
- 实际上，该程序不需要做任何事情
与输入有关。家庭作业
说程序应该......。 （强调我的），和
应该仅仅是一个提示。要求总是用应表示正确表达。 （和禁止
，不得），如
C语言标准第4节所述。
我希望这可以帮助你获得你应得的成绩。
-
Er ********* @ sun.com
The C language Standard has nothing to say about speed
and "efficiancy," but I think this program will be hard to
beat:
int main(void) {
return 0;
}
You may be wondering why this program works as required, and
your professor may wonder the same thing. The answer lies in
a close reading of the homework statement:
- Output is only required *if* "aaa" or "aba" is
detected. This program detects neither (nowhere
does the homework assignment state a requirement
that anything be detected), and is thus relieved
of any responsibility to produce output.
- The program is expressly forbidden to detect
"sequences within sequences." The stream of
input characters is a sequence (note the use of
the term in the two examples), so the program is
forbidden to detect anything in its input.
- The program is required to "monitor" its input,
but the verb "monitor" is not defined by the C
language Standard, nor by the homework assignment.
Therefore we are free to define it in the manner
we find most convenient. The sixth definition
given by http://www.yourdictionary.com for the
transitive verb "monitor" is "to direct," and
the program above "directs" the input to the
highly efficient bit bucket.
- Actually, the program is not required to do anything
at all with or to the input. The homework assignment
says "The program SHOULD ..." (emphasis mine), and
"should" is merely a hint. A requirement is always
properly expressed with "shall" (and a prohibition
with "shall not"), as described in Section 4 of the
C language Standard.
I hope this helps you get the grade you deserve.
--
Er*********@sun.com
Andy Green写道：
Andy Green wrote:
重点在于效率和速度这是练习：
程序应该从键盘监视可能无限的字符流（标准输入）。如果它检测到序列aaa，则它输出0。如果它检测到序列aba，它输出1。
不检测序列内的序列。程序在检测到输入结束时应该干净地退出。例如：
以下序列aababaaabaaa<输入结束>将产生以下结果：100
以下序列aaababaaaabbababa<输入结束>会产生以下结果：0101
任何接受者？
Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:
The following sequence aababaaabaaa<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101
Any takers?
这在lexing和解析下更多。 IMO，自然的
行动方案是为这项任务创建一种语言。
类似于：
zero_sequence :: = aaa
one_sequance :: = aba
通过lex或flex等程序运行，生成
a解析表。然后写一个程序来支持解析
表。保留这些作品，因为你需要它们来做你的下一个家庭作业。
或者一个简单的状态图可以帮助你：
b + --- +
+ ------> | 4 | - +
| + --- + |
| |
+ --- + a + --- + a + --- + |
O - > | 1 | ---> | 2 | ---> | 3 | |
+ --- + + --- + + --- + |
^ | | |
| vv |
+ --------------------------- +
状态1：保持这种状态，直到检测到a为止。
状态2：如果检测到a，则转换到状态3。 />
如果检测到b，则转换到状态4.
否则转换到状态1.
状态3：如果检测到a，则打印0。
在所有情况下转换到状态1.
状态4：如果是检测到'a''，打印''1'。
在所有情况下转换到状态1.
如果在任何情况下检测到EOF状态，该程序应该退出（即状态5）。
现在，编码。
-
Thomas Matthews
C ++新闻组欢迎辞：
http://www.slack.net/~shiva/welcome.txt
C ++常见问题： http://www.parashift.com/c++-faq-lite
C常见问题： http：//www.eskimo。 com /~scs / c-faq / top.html
alt.comp.lang.learn.c-c ++ faq：
http://www.raos.demon.uk/acllc-c++/faq.html
其他网站：
http://www.josuttis.com - C ++ STL图书馆书
This falls more under lexing and parsing. IMO, the natural
course of action is to create a language for this assignment.
Something like:
zero_sequence ::= a a a
one_sequance ::= a b a
Run this through a program such as lex or flex to generate
a parse table. Then write a program to support the parse
table. Keep these pieces, as you will need them to do
your next homework assignments.
Or perhaps a simple state diagram would help you:
b +---+
+------> | 4 | --+
| +---+ |
| |
+---+ a +---+ a +---+ |
O -> | 1 | ---> | 2 | ---> | 3 | |
+---+ +---+ +---+ |
^ | | |
| v v |
+---------------------------+
State 1: stay in this state until an ''a'' is detected.
State 2: if an ''a'' is detected, transition to state 3.
if a ''b'' is detected, transition to state 4.
Otherwise transition to state 1.
State 3: if an ''a'' is detected, print ''0''.
Transition in all cases to state 1.
State 4: if an ''a'' is detected, print ''1''.
Transition in all cases to state 1.
If an EOF is detected in any state, the program should
exit (i.e. state 5).
Now, code it up.
--
Thomas Matthews
C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
这篇关于序列匹配练习的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
