當(dāng)前位置:首頁 > 芯聞號(hào) > 充電吧
[導(dǎo)讀]Description An ascending sorted sequence of distinct values is one in which some form of a less-than

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

輸入樣例


4 6
A A B C B A 3 2
A B 26 1
A 0 0


輸出樣例
Sorted sequence determined after 4 relations: ABCD.

Inconsistency found after 2 relations.

Sorted sequence cannot be determined.

我們現(xiàn)在只看樣例:4和6的含義分別是:

4表示表達(dá)式中一共含有4個(gè)字符,也就是說我們需要排序的是4個(gè)樣例,6呢,就是需要用戶輸入6個(gè)表達(dá)式,我們根據(jù)這兩個(gè)數(shù)值和相應(yīng)的表達(dá)式,去推算字符的先后順序

,可能會(huì)有三種結(jié)果,一種當(dāng)然是排序成功,比如第一個(gè)輸入,一種是會(huì)有邏輯沖突,比如第二個(gè)輸入,一種就是條件不足,不能判斷

我的算法思想是這樣的,定義一個(gè)結(jié)構(gòu)體,該結(jié)構(gòu)體有三個(gè)變量,一個(gè)是key表示字符,一個(gè)是value,表示權(quán)重,一個(gè)就是布爾變量,表示該值是否已經(jīng)參加運(yùn)算

1.根據(jù)用戶輸入初始換結(jié)構(gòu)體數(shù)組變量(chain_head),將相應(yīng)的key值存到結(jié)構(gòu)體當(dāng)中,value則是UNSET,布爾類型變量則是false,表示還未參加到運(yùn)算當(dāng)中,

2.接下來,計(jì)算第n個(gè)表達(dá)式(n初始化成0),我們獲取第n個(gè)表達(dá)式的第一個(gè)和第三個(gè)字符,分別獲得該key在結(jié)構(gòu)體數(shù)組中的索引,index_a和index_b,這樣需要比較的就是

chain_head[index_a]和chain_head[index_b]了,首先看下chain_head[index_a].value是否小于chain_head[index_b].value,如果小于,則不進(jìn)行任何操作,繼續(xù)計(jì)算第n+1個(gè)

表達(dá)式,如果chain_head[index_a].value大于chain_head[index_b].value并且,chain_head[index_b].FirstApper=true(index_b的結(jié)構(gòu)體從未參加運(yùn)算),則表示邏輯沖突,停

止循環(huán),輸出結(jié)構(gòu),如果chain_head[index_a].value==chain_head[index_b].value則chain_head[index_b].value=chain_head[index_a].value+1;即可,然后進(jìn)行第n+1個(gè)表達(dá)

式的計(jì)算,繼續(xù)進(jìn)行第二步的運(yùn)算

3.清理現(xiàn)場,輸出結(jié)果

源代碼如下:

// Sort_It.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#include "stdafx.h"
#include
using namespace std;
/****************************************************************************************************************
***文件名稱:Sort_It.cpp
***文件描述:根據(jù)表達(dá)式對(duì)字符進(jìn)行排序
****************************************************************************************************************/
typedef struct {
	char key;
	int value;	
	bool FirstApper;
}Key_Value;
Key_Value* chain_head=NULL;
int  nCount=0;//需要排序的字符個(gè)數(shù)
int  nCur_Count=0;//當(dāng)前已經(jīng)賦值的個(gè)數(shù)
int result=0;
#define DONE  1
#define INCONSIST 2
#define UNENOUGH 3
#define UNSET  1
void operation(char key_a,char key_b);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///函數(shù)名稱:TestOver
///函數(shù)描述:檢測根據(jù)當(dāng)前獲得信息,檢測是否已經(jīng)可以完成排序(value的值疊加,如果等于1,2,3的和則表示排序完成)
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool TestOver(Key_Value* head)
{
	int nSum_1=0,nSum=0;
	for(int i=0;i