项链编程代码(代码编程火影忍者)

编程实例取珠子

你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。这里是n=29的二个例子:

rbbrbrrb

rbrrrw

图片A图片B

r代表红色的珠子

b代表蓝色的珠子

w代表白色的珠子

第一和第二个珠子在图片中已经被作记号。

图片A中的项链可以用下面的字符串表示：

brbrrrbbbrrrrrbrrbbrbbbbrrrrb.

假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。确定应该在哪里打破项链来收集到最大多数的数目的子。Example举例来说，在图片A中的项链，可以收集到8个珠子,在珠子9和珠子10或珠子24和珠子25之间打断项链。在一些项链中，包括白色的珠子如图片B所示。当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。表现项链的字符串将会包括三符号r，b和w。写一个程序来确定从一条被供应的项链最大可以被收集珠子数目。

PROGRAMNAME:beads

INPUTFORMAT

第1行:N,珠子的数目

第2行:一串度为N的字符串,每个字符是r，b或w。

SAMPLEINPUT(filebeads.in)

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUTFORMAT

单独的一行包含从被供应的项链可以被收集的珠子数目的最大值。

SAMPLEOUTPUT(filebeads.out)

#include

#defineBEAD_MAX350

charoriLace[BEAD_MAX+1]="";

intlen;

enumBeadColor

white=0,

black=1,

red=2,

structSBead

enumBeadColorcolor;

intamount;

structSBead*prev;

structSBead*next;

structSBead*necklace=NULL;

//structSBead*newSBead(charcolor);

intcompressNecklace();

intsearchMax();

intsearchLeft(enumBeadColor,structSBead*);

intsearchRight(enumBeadColor,structSBead*);

intdeleteNecklace();

main()

FILE*fin=fopen("beads.in","r");

FILE*fout=fopen("beads.out","w");

intmaximum;

fscanf(fin,"%d%*c",&len);

fscanf(fin,"%s",oriLace);

compressNecklace();

maximum=searchMax();

fprintf(fout,"%d\n",maximum);

deleteNecklace();

fclose(fin);

fclose(fout);

return0;

intcompressNecklace()

inti=0,j=0;

charc_i,c_j;

intcolor=0;

intcount=0;

structSBead*pBead,*curBead;

while(i

c_i=oriLace[i];

pBead=(structSBead*)malloc(sizeof(structSBead));

switch(c_i)

casew:color=0;

break;

caseb:color=1;

break;

caser:color=2;

break;

default:break;

pBead->color=color;

for(j=i;j

c_j=oriLace[j];

if(c_j!=c_i)

break;

pBead->amount=j-i;

if(necklace==NULL)

necklace=curBead=pBead;

pBead->next=curBead;

pBead->prev=necklace;

necklace->prev=curBead->next=pBead;

pBead->prev=curBead;

pBead->next=necklace;

curBead=pBead;

return0;

intsearchMax()

structSBead*pBead,*curBead;

intrl,rr,bl,br;//red_left,red_right,black_lest,black_right

intmax_l,max_r,max=0;

if(necklace->next==necklace)

returnnecklace->amount;

pBead=necklace;

rl=searchLeft(red,pBead);

bl=searchLeft(black,pBead);

rr=searchRight(red,pBead);

br=searchRight(black,pBead);

max_l=(rl>bl)?rl:bl;

max_r=(rr>br)?rr:br;

max=((max_l+max_r)>max)?(max_l+max_r):max;

pBead=pBead->next;

}while(pBead!=necklace);

max=(len>max)?max:len;

returnmax;

intsearchLeft(enumBeadColorsouColor,structSBead*souBead)

intcumulative=0;

structSBead*pBead=souBead;

if((pBead->color!=souColor)&&(pBead->color!=white))

return0;

cumulative=pBead->amount;

pBead=pBead->prev;

while((pBead!=souBead)

&&((pBead->color==souColor)

||(pBead->color==white)

cumulative+=pBead->amount;

pBead=pBead->prev;

returncumulative;

intsearchRight(enumBeadColorsouColor,structSBead*souBead)

intcumulative=0;

structSBead*pBead;

pBead=souBead=souBead->next;

if((pBead->color!=souColor)&&(pBead->color!=white))

return0;

cumulative=pBead->amount;

pBead=pBead->next;

while((pBead!=souBead)

&&((pBead->color==souColor)

||(pBead->color==white)

cumulative+=pBead->amount;

pBead=pBead->next;

returncumulative;

return0;

intdeleteNecklace()

structSBead*pBead,*curBead;

pBead=necklace;

necklace->prev->next=NULL;

while(pBead!=NULL)

curBead=pBead;

pBead=pBead->next;

free(curBead);

return0;

本回答由网友推荐

C语言链串

/* turbo c 2.0 */ #include#include #define null 0 #define true 1 #define false 0 typedef struct _string { char ch; struct _string *next; }linkstring; /* 创建链串 */ linkstring * creatlistlink() { char ch; linkstring *r,*s,*head; head = null; r = null; ch=getchar(); while(ch!=\n) /* 回车表示结束 */ { s=malloc(sizeof(linkstring)); s->ch=ch; if(head ==null) head=s; else r->next=s; r=s; ch=getchar(); } if(r!=null) r->next=null; ch = \0; return head; } /* 输出链串 */ void show(linkstring * head) { linkstring *p = head; if(p == null) printf("链表为null!"); else do { printf("%c",p->ch); p = p->next; }while(p!=null); printf("\n"); } linkstring *linkstrmatch(linkstring *t,linkstring *s) { linkstring *s,*t,*shift; t=t;s=s; shift = t; while(t && s) { if(t->ch == s->ch) { t=t->next;s=s->next; } else { shift = shift ->next; t= shift; s=s; } } if(s == null) return shift; else return null; } main() { int i; linkstring *str1 = null, *str2=null; clrscr(); printf("str1:"); str1 = creatlistlink(); printf("str2:"); str2 = creatlistlink(); show(str1); show(str2); printf("%c \n",linkstrmatch(str1,str2)->ch); getch(); }