一个七边形，把1到14这些数摆在它的每条边上，每个数用一次，使每条边的和是26 - C语言论坛

第 21 楼

得分:0

思想：
1 找出3数和为26的所有组合（3个数范围在1-14）
2 7条边用1中的组合试邻边有且只有1个数相同

实现的时候：flag用于剔除重复，第N位表示N，比如flag=(0000011010)b 即表示（1，3，4）的组合

程序代码：

// TempTemp.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MY_DEBUG  (0)
#define MAX_ROW   (100)
#define NUM_MAX   (14)
#define SIDES_SUM (26)

int SideCombArray[MAX_ROW][3] = {0};
int SideCombFlag[MAX_ROW] = {0};


inline int GetSideCombFlag(int i, int j, int k)
{
    int flag = 0;

    flag |= 1<<i;
    flag |= 1<<j;
    flag |= 1<<k;
    
    return flag;
}

bool IsSideCombAlreadyExist(int SideCombFlag[MAX_ROW],int FlagToVerify, int Count)
{
    int i = 0;

    for (i=0; i<Count; i++)
    {
        if (SideCombFlag[i] == FlagToVerify)
        {
            return true;
        }
    }

    return false;
}

int SideCombCount = 0;
void GenSideSumArray()
{
    int i = 0;
    int j = 0;
    int k = 0;

    for (i=1; i<=NUM_MAX; i++)
    {
        for (j=1; j<=NUM_MAX; j++)
        {
            if (j==i) continue;
            for (k=1; k<=NUM_MAX; k++)
            {
                if (k==i || k==j) continue;
                if (SIDES_SUM == i+j+k)
                {
                    int Flag = GetSideCombFlag(i,j,k);

                    if (!IsSideCombAlreadyExist(SideCombFlag, Flag, SideCombCount))
                    {
                        SideCombFlag[SideCombCount] = Flag;
                        SideCombArray[SideCombCount][0] = i;
                        SideCombArray[SideCombCount][1] = j;
                        SideCombArray[SideCombCount++][2] = k;
#if MY_DEBUG
    printf("%d + %d + %d = %d\n",i,j,k,SIDES_SUM);
#endif
                    }
                }
            }
        }            
    }
#if MY_DEBUG
    printf("Count = %d\n\n",SideCombCount);
#endif

    return;
}

bool IsSideCombAlreadyPicked(int Side[7], int SideIndex, int FlagIndex)
{
    int i = 0;

    for (i=0; i<7; i++)
    {
        if (i != SideIndex && Side[i] == FlagIndex)
        {
            return true;
        }
    }

    return false;
}

bool IsOnlySameOne(int FlagIndex1, int FlagIndex2)
{
    int FlagTemp = SideCombFlag[FlagIndex1] & SideCombFlag[FlagIndex2];
    int i = 0;
    int Count = 0;

    for (i=1; i<=14; i++)
    {
        if (FlagTemp & (1<<i))
        {
            Count++;
            if (Count > 1)
            {
                return false;
            }
        }
    }

    return (Count == 1);

}

bool IsSideCaseOk(int Side[7])
{
    int i = 0;
    int NumCount[14] = {0};
    int PointCount = 0;


    for (i=0; i<7; i++)
    {
        NumCount[SideCombArray[Side[i]][0]-1]++;
        NumCount[SideCombArray[Side[i]][1]-1]++;
        NumCount[SideCombArray[Side[i]][2]-1]++;
    }

    for (i=0; i<14; i++)
    {
        if (NumCount[i] == 0 || NumCount[i] > 2)
        {
            return false;
        }
        if (NumCount[i] == 2)
        {
               PointCount++;
        }
    }

    if (PointCount != 7)
    {
        return false;
    }

    return true;
}

int GetTopPoint(int Side[7], int SideIndex)
{
    int i = 0;
    int PrevIndex = (SideIndex - 1 + 7) % 7;
    int Point = SideCombFlag[Side[SideIndex]] & SideCombFlag[Side[PrevIndex]];

    for (i=1; i<=14; i++)
    {
        if (Point & (1<<i))
        {
            return i; 
        }
    }

    return -1;
}

void PrintSeven(int Side[7])
{
    int i = 0;
    int Point[14] = {0};

    printf("\nfind!\n");
    for (i=0; i<7; i++)
    {
        Point[i*2] = GetTopPoint(Side,i);
        if (i)
        {
            Point[i*2-1] = SIDES_SUM - Point[i*2] - Point[i*2 - 2];
            printf("第%d条边: %d--%d--%d\n",i,Point[i*2 - 2],Point[i*2 - 1],Point[i*2]);
        }
        
    }
    Point[i*2 - 1] = SIDES_SUM - Point[0] - Point[i*2 - 2];
    printf("第%d条边: %d--%d--%d\n",i,Point[i*2 - 2],Point[i*2 - 1],Point[0]);


    return;
}

void ChooseSide()
{
    int Side[7] = {0};

    for (Side[0]=0; Side[0]<SideCombCount; Side[0]++)
    {
        for (Side[1]=0; Side[1]<SideCombCount; Side[1]++)
        {
            if (IsSideCombAlreadyPicked(Side, 1, Side[1])) continue;
            if (!IsOnlySameOne(Side[1],Side[0])) continue;
            for (Side[2]=0; Side[2]<SideCombCount; Side[2]++)
            {
                if (IsSideCombAlreadyPicked(Side, 2, Side[2])) continue;
                if (!IsOnlySameOne(Side[2],Side[1])) continue;
                for (Side[3]=0; Side[3]<SideCombCount; Side[3]++)
                {
                    if (IsSideCombAlreadyPicked(Side, 3, Side[3])) continue;
                    if (!IsOnlySameOne(Side[3],Side[2])) continue;
                    for (Side[4]=0; Side[4]<SideCombCount; Side[4]++)
                    {
                        if (IsSideCombAlreadyPicked(Side, 4, Side[4])) continue;
                        if (!IsOnlySameOne(Side[4],Side[3])) continue;
                        for (Side[5]=0; Side[5]<SideCombCount; Side[5]++)
                        {
                            if (IsSideCombAlreadyPicked(Side, 5, Side[5])) continue;
                            if (!IsOnlySameOne(Side[5],Side[4])) continue;
                            for (Side[6]=0; Side[6]<SideCombCount; Side[6]++)
                            {
                                if (IsSideCombAlreadyPicked(Side, 6, Side[6])) continue;
                                if (!IsOnlySameOne(Side[6],Side[5])) continue;
                                if (!IsOnlySameOne(Side[0],Side[6])) continue;

                                if (IsSideCaseOk(Side))
                                {
#if MY_DEBUG
    printf("1th: %d-%d-%d\n",SideCombArray[Side[0]][1],SideCombArray[Side[0]][2],SideCombArray[Side[0]][3]);
    printf("7th: %d-%d-%d\n",SideCombArray[Side[6]][1],SideCombArray[Side[6]][2],SideCombArray[Side[6]][3]);
#endif
                                    PrintSeven(Side);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}


int main()
{
    GenSideSumArray();
    ChooseSide();
    return 0;
}

[ 本帖最后由 njkido 于 2011-4-9 02:19 编辑 ]

第 22 楼

得分:0

以下是引用njkido在2011-4-9 02:03:29的发言：

思想：
1 找出3数和为26的所有组合（3个数范围在1-14）
2 7条边用1中的组合试邻边有且只有1个数相同

实现的时候：flag用于剔除重复，第N位表示N，比如flag=(0000011010)b 即表示（1，3，4）的组合

// TempTemp.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
#include
#include

#define MY_DEBUG  (0)
#define MAX_ROW   (100)
#define NUM_MAX   (14)
#define SIDES_SUM (26)

int SideCombArray[MAX_ROW][3] = {0};
int SideCombFlag[MAX_ROW] = {0};

inline int GetSideCombFlag(int i, int j, int k)
{
    int flag = 0;

    flag |= 1<

您真是高手啊，太感谢了！我原来也用组合做过，就是没有做出来，后来我又这样想：七条边，每条边之和为26，7*26=182，1到14的数字相加等于105，182-105=77，这个77就是七边形的七个顶点上的数字的和，所以每条边的中点的数字之和就是105-77=28，也就是说顶点的数字只能是由：8，9，10，11，12，13，14这些数字构成，而中点的数字只能由：1，2，3，4，5，6，7这些数字构成，我尝试了用数组排序的办法去实现，但由于才自学C语言没多久，把脑壳搞大了也没有搞成。

只有不断学习人生才有乐趣

第 23 楼

得分:0

以下是引用kwxx在2011-4-8 20:34:03的发言：

不好意思，是我分析错了。

兄弟啊，我是这样想的，可我自己没有实现，我的想法是这样的：七条边，每条边之和为26，7*26=182，1到14的数字相加等于105，182-105=77，这个77就是七边形的七个顶点上的数字的和，所以每条边的中点的数字之和就是105-77=28，也就是说顶点的数字只能是由：8，9，10，11，12，13，14这些数字构成，而中点的数字只能由：1，2，3，4，5，6，7这些数字构成，我尝试了用数组排序的办法去实现，但由于才自学C语言没多久，把脑壳搞大了也没有搞成。

只有不断学习人生才有乐趣

第 24 楼

得分:2

楼上分析得太好了，继续：
1 周围可以是 11 1 14，或 12 1 13
2 周围可以是 10 2 14，或 11 2 13
3 周围可以是 9 3 14，或 10 3 13，或 11 3 12
……

第 25 楼

得分:0

以下是引用rjsp在2011-4-9 10:27:19的发言：

楼上分析得太好了，继续：
1 周围可以是 11 1 14，或 12 1 13
2 周围可以是 10 2 14，或 11 2 13
3 周围可以是 9 3 14，或 10 3 13，或 11 3 12
……

是这样的？

程序代码：

        int a,b,c,j=0;
        for(a=8;a<15;a++) {
                for(c=8;c<15;c++) {
                        for(b=1;b<8;b++) {
                                if(26==a+b+c&&a!=c) {
                                        printf ("%i\t%i+%i+%i=26\n",j,a,b,c);j++
;
                                }
                        }
                }
        }
}

善人者，不善人之师；不善人者，善人之资。不贵其师，不爱其资，虽智大迷。

第 26 楼

得分:0

以下是引用kuangyitian在2011-4-9 06:55:36的发言：

兄弟啊，我是这样想的，可我自己没有实现，我的想法是这样的：七条边，每条边之和为26，7*26=182，1到14的数字相加等于105，182-105=77，这个77就是七边形的七个顶点上的数字的和，所以每条边的中点的数字之和就是105-77=28，也就是说顶点的数字只能是由：8，9，10，11，12，13，14这些数字构成，而中点的数字只能由：1，2，3，4，5，6，7这些数字构成，我尝试了用数组排序的办法去实现，但由于才自学C语言没多久，把脑壳搞大了也没有搞成。

善人者，不善人之师；不善人者，善人之资。不贵其师，不爱其资，虽智大迷。

第 27 楼

得分:0

以下是引用ansic在2011-4-9 10:43:15的发言：

是这样的？

        int a,b,c,j=0;
        for(a=8;a<15;a++) {
                for(c=8;c<15;c++) {
                        for(b=1;b<8;b++) {
                                if(26==a+b+c&&a!=c) {
                                        printf ("%i\t%i+%i+%i=26\n",j,a,b,c);j++
;
                                }
                        }
                }
        }
}

兄弟啊，这段代码只是把符合条件的34种组合排出来了，这个我昨天也这样做出来了，也是34种，问题是怎样把他符合条件的14个数字组合到一起，我就不知道怎样写代码了，我在尝试用数组排序解决，但我还没有搞成

只有不断学习人生才有乐趣

第 28 楼

得分:0

前面有一位高人贴了一段代码出来，我验证了，是对的，但现阶段对于我来讲复杂了一点，我在寻求简单的方法

只有不断学习人生才有乐趣

第 29 楼

得分:0

回复 28楼 kuangyitian

你好，请问您找到简单的方法了吗？是否可以用回溯法呢？