有趣的问题（高分相赠）

设一个环上有编号为0~n-1的n粒不同颜色的珠子（每粒珠子颜色用字母表示，n粒珠子颜色由输入的字符串表示）。以环上某两粒珠子间为断点，从断点一方按顺时针方向取走连续同色的珠子，又从断点另一方按逆时针方向对剩下珠子取走连续同色的珠子，两者之和为该断点可取走的珠子粒数。移动断点，能取走的珠子数不尽相同。设计一个C语言程序找出可以取走最多的珠子数及断点的位置。程序中用双向链表存储字符串。
程序如下，结果不正确，请高人指点，企盼

#include <iostream.h>
//#include <alloc.h>

/* --------------------------------- */
/*        定义循环双链表结构             */
/* ----------------------------------*/
struct cdlist
{        
int data;
struct cdlist* front;
struct cdlist* back;
};
//定义新链表类型
typedef struct cdlist dbeads;
//定义新链表指针
typedef dbeads* cdlink;

/* --------------------------------- */
/*       循环双向链表的节点插入      */
/* ----------------------------------*/
cdlink insertnode(cdlink head,cdlink ptr,int value)
{
cdlink new_node;

//new_node = (cdlink) malloc(sizeof(dbeads));
new_node = new dbeads;
if (!new_node)
return NULL;
new_node->data = value;

if (head == NULL)              //如果链表是空地
{
new_node->front = new_node;
new_node->back = new_node;
return new_node;
}

if (ptr == NULL)            //插在第一个节点之前成为链表地开始
{
head->back->front = new_node;
new_node->front = head;
new_node->back = head->back;
head->back = new_node;
}
else                       //插在节点之后
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
return head;
}

/* --------------------------------- */
/*       运用循环双向链表取走        */
/*       最多的珠子数及断点的位置    */
/* ----------------------------------*/
void main(){
int count = 0;
cdlink head = NULL;
char datatemp;
cdlink tempptr = NULL;
cdlink now = NULL;
char list[100];
cout<<"请输入串珠"<<endl;
cin.get(list,100);
//int i;
        
        /*生成链表数据*/
cout << "用户已输入数据：" << endl;
for (i = 0; list[i] != '\0'; i++)
{
head = insertnode(head,NULL,list[i]);
count++;
cout <<list[i];
}
cout << endl;

if (head == NULL)
{
  cout << "内存分配失败" <<endl;
  //exit(0);
  return;
}

now = head;
tempptr = now;
int beadscnt;
for (int i = 0; i < count-1; i++)
{    
        beadscnt = 0;
        tempptr = NULL;
tempptr = now;
        
datatemp = tempptr->data;
cout << datatemp;
for (int i = 0; i < count-1; i++)
{
int fbeadscnt = 0;
tempptr = tempptr->front;
char indatatemp = tempptr->data;
if (datatemp != indatatemp) 
{
continue  
}
else
{
if (i > fbeadscnt)
{
continue
}
else
{
fbeadscnt++;
}

}
cout << indatatemp;
beadscnt += fbeadscnt;
}

tempptr = now;
datatemp = tempptr->data;
for (int i = 0; i < count-1; i++)
{
int bbeadscnt = 0;
tempptr = tempptr->back;
char indatatemp = tempptr->data;
if (datatemp != indatatemp) 
{
continue  
}
else
{
if (i > bbeadscnt)
{
continue
}
else
{
bbeadscnt++;
}

}
        beadscnt += bbeadscnt;
}     
cout << beadscnt;  
cout << endl; 

now = now->front;
}
}

7 个解决方案

#1

你先说说你觉得哪不对，你的分析。

#2

前年（或大前年）初程的试题，找来看看吧

#3

只是漏了几个分号,好着呢！

#4

嗯
很好 很好

#5

顺时针取走的球颜色和逆时针取走球颜色相同吗，还是各自相同？

#6

//看看这个，如有问题，欢迎指正


/*-------------------------------------
设一个环上有编号为0~n-1的n粒不同颜色的珠子
（每粒珠子颜色用字母表示，n粒珠子颜色由输入
的字符串表示）。以环上某两粒珠子间为断点，
从断点一方按顺时针方向取走连续同色的珠子，
又从断点另一方按逆时针方向对剩下珠子取走
连续同色的珠子，两者之和为该断点可取走的
珠子粒数。移动断点，能取走的珠子数不尽相同。
设计一个C语言程序找出可以取走最多的珠子数及
断点的位置。程序中用双向链表存储字符串。

程序如下，结果不正确，请高人指点，企盼
*/
#include <iostream.h>
//#include <alloc.h>

/* --------------------------------- */
/*        定义循环双链表结构             */
/* ----------------------------------*/
struct cdlist
{        
int data;
struct cdlist* front;
struct cdlist* back;
};
//定义新链表类型
typedef struct cdlist dbeads;
//定义新链表指针
typedef dbeads* cdlink;

/* --------------------------------- */
/*       循环双向链表的节点插入      */
/* ----------------------------------*/
cdlink insertnode(cdlink head,cdlink ptr,int value)
{
cdlink new_node;

new_node = new dbeads;
if (!new_node)
return NULL;
new_node->data = value;

if (head == NULL)              //如果链表是空地
{
new_node->front = new_node;
new_node->back = new_node;
return new_node;
}

if (ptr == NULL)            //插在第一个节点之前成为链表地开始
{
head->back->front = new_node;
new_node->front = head;
new_node->back = head->back;
head->back = new_node;
}
else                       //插在节点之后
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
return head;
}

//my functions
cdlink deletenode(cdlink head,cdlink ptr)
{
//assert
if(!head)
{
return head;
}
if(!ptr)
{
return head;
}
if(head == (void *)0xdddddddd || ptr == (void *)0xdddddddd)
{
cout<<"error"<<endl;
return NULL;
}
if (ptr == head && head->back == head)
{
delete head;
head = NULL;
return NULL;
}

ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
if (ptr == head)
{
head = ptr->front; 
}
delete ptr;
ptr = NULL;
return head;
}



int takenode(cdlink phead)
{
cdlink pnow = NULL;
cdlink ptmp = NULL;
pnow = phead;
int icount = 0;
int data = 0;
bool flag = false;
data = phead->data;

//NUll list
if(!phead)
{
return icount;
}

//only one node!
if(phead->front == phead)
{
return icount;
}
while(true)
{
pnow = pnow->front;
if(!pnow)
{
break;
}
if(pnow == phead && flag == false)
{
break;
}
if(data == pnow->data)
{
if(flag == false)
{
phead = deletenode(phead,pnow->back);
icount++;
}

ptmp = pnow->back;
phead = deletenode(phead,pnow);
pnow = ptmp;
icount++;
if(!phead)
{
break;
}
flag = true;
}
else
{
flag = false;
data = pnow->data;
}
}
//--------------------backward---------------------
//NUll list
if(!phead)
{
return icount;
}
while(true)
{
pnow = pnow->back;
if(pnow = phead)
{
break;
}
if(!pnow)
{
break;
}
if(data == pnow->data)
{
if(flag == false)
{
phead = deletenode(phead,pnow->front);
icount++;
}
ptmp = pnow->back;
phead = deletenode(phead,pnow);
pnow = ptmp;
icount++;
if(!phead)
{
break;
}
flag = true;
}
else
{
flag = false;
data = pnow->data;
}
}
return icount;

}

/* --------------------------------- */
/*       运用循环双向链表取走        */
/*       最多的珠子数及断点的位置    */
/* ----------------------------------*/
void main(){
int count = 0;
cdlink head = NULL;
cdlink tempptr = NULL;
cdlink now = NULL;
char list[100];
cout<<"请输入串珠"<<endl;
cin.get(list,100);
int i = 0;
    int j = 0;
int total = 0;
    /*生成链表数据*/
cout << "用户已输入数据：" << endl;
for (i = 0; list[i] != '\0'; i++)
{
count++;
cout <<list[i]<<"   ";
}
cout << endl;
cout<<"位置"<<"\t"<<"数目"<<"\t"<<endl;
for (i=0;i<count;i++)
{
head = NULL;
for(j = 0; j < count; j++)
{
head = insertnode(head,NULL,list[j]);
}
for(j = 0; j<i; j++)
{
head = head->front;
}
total = takenode(head);
cout<<i<<"\t"<<total<<endl;
}

}

#7

/* 按照前后颜色各自相同写的 */
#include <stdio.h>

typedef struct ListStruc
{
    char               cval;
    struct ListStruc  *pPrevList;
    struct ListStruc  *pNextList;
}T_ListStruc;

T_ListStruc *ps_List;

int insert(char c)
{
    T_ListStruc *pList;
    
    pList = (T_ListStruc *)malloc(sizeof(T_ListStruc));
    if (pList == NULL)
        return -1;
    pList->cval = c;
    pList->pPrevList = NULL;
    pList->pNextList = ps_List;
    if (ps_List != NULL)
    {
        ps_List->pPrevList = pList;
    }
    ps_List = pList;
    return 0;
}

void main()
{
    char cput[50], c;
    int  iLoop = 0, lastcount, count, pos;
    T_ListStruc *ptmpList, *pPosList;

    memset((void *)cput, 0, (size_t)sizeof(cput));
    ps_List = NULL;
    scanf("%s", cput);
    while(cput[iLoop] != '\0')
    {
        insert(cput[iLoop++]);
    }
    ptmpList = ps_List;
    lastcount = 0;
    iLoop     = 0;
    while (ptmpList != NULL)
    {
        count = 1;
        pPosList = ptmpList;
        c = ptmpList->cval;
        while (pPosList->pPrevList != NULL)
        {
            pPosList = pPosList->pPrevList;
            if (pPosList->cval != c)
            {
                break;
            }
            count += 1;
        }
        pPosList = ptmpList;
        while (pPosList->pNextList != NULL)
        {
            pPosList = pPosList->pNextList;
            if (pPosList == ptmpList->pNextList)
                c = pPosList->cval;
            else if (pPosList->cval != c)
            {
                break;
            }
            count += 1;
        }
        printf("Pos=%d, count= %d\n", iLoop, count);
        lastcount = (lastcount > count) ? lastcount : count;
        if (lastcount == count)
            pos = iLoop;
        ptmpList = ptmpList->pNextList;
        iLoop++;
    }
    printf("Pos=%d, count= %d\n", pos, lastcount);
};