IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> си и паскаль, смотреть всем программистам
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


// lb-sim-batch
// © A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos, 2006
//
// Purpose:
//
// Computes the maximum cut of a random generated graph G in G(n,m)
// from average degree dl to average degree du, with step dstep
// n=2^k is the number of nodes of G
// m=d*n/2 is the number of edges of G
//
// Syntax:
//
// lb-sim-batch [k] [dl] [du] [step] [output file name]
// k is the exponent of a power of 2, while
// dl is the lower value of average degree of G
// du is the upper value of average degree of G
// dstep is the value of increasing the average degree of G
// The output is directed to output file name (also to the standand output)
//
// Output format:
//
// number of nodes, average degree, and the maximum cut of graph G
//
// Reference paper:
//
// A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos,
// Approximating almost all instances of Max-Cut within a ratio above the H{\aa}stad threshold.
// In Proc. of ESA 2006, LNCS 4168, pp. 432--443, 2006
//


#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


#define UNCOLORED -1
#define RED 0
#define BLUE 1
#define MAXVARS 100

typedef struct _Tneigh
{
int who;
struct _Tneigh *next;
} Tneigh;

typedef struct
{
Tneigh *neigh;
int degree;
} Tnode;

typedef struct
{
int neighcolored[2];
int mycolor;
} Tnodecolor;

Tnode *nodes;
Tnodecolor *nodecolors;

int k, numofnodes, numofedges;
double c, cl, cu, cstep;
double d, dl, du, dstep;

FILE *fp;
int decimation_cut=0;


void *alloc (size_t n)
{
void *ret;

ret = malloc(n);
if (ret == 0)
{
printf ("out of memory! Exiting...\n");
exit(0);
}
return (ret);
}

int randomnumber (int size)
{
return (rand() % size);
}

void initgraph ()
{
int i;

nodes = (Tnode *) alloc (numofnodes*sizeof (Tnode));
nodecolors = (Tnodecolor *) alloc (numofnodes*sizeof(Tnodecolor));

for (i=0;i<numofnodes;++i)
{
nodes[i].degree = 0;
nodes[i].neigh = 0;
}

}

void freegraph ()
{
int i;
Tneigh *p, *pnext;

for (i=0;i<numofnodes;++i)
{
p=nodes[i].neigh;
while (p)
{
pnext = p->next;
free (p);
p=pnext;
}
}

free (nodes);
free (nodecolors);
}

void randomgraph ()
{
int i, distinct, endpoint1, endpoint2;
Tneigh *p, *prev;

for (i=0;i<numofedges;++i)
{
endpoint1 = randomnumber (numofnodes);
distinct = 0;
while (!distinct)
{
endpoint2 = randomnumber (numofnodes);
if (endpoint2 != endpoint1)
distinct = 1;
}
if (nodes[endpoint1].degree == 0)
{
nodes[endpoint1].neigh = (Tneigh *) alloc (sizeof(Tneigh));
nodes[endpoint1].neigh->who = endpoint2;
nodes[endpoint1].neigh->next = 0;
}
else
{
p = nodes[endpoint1].neigh;
while (p)
{
prev = p;
p = p->next;
}
p = (Tneigh *) alloc (sizeof(Tneigh));
prev->next = p;
p->who = endpoint2;
p->next = 0;
}
nodes[endpoint1].degree++;

if (nodes[endpoint2].degree == 0)
{
nodes[endpoint2].neigh = (Tneigh *) alloc (sizeof(Tneigh));
nodes[endpoint2].neigh->who = endpoint1;
nodes[endpoint2].neigh->next = 0;
}
else
{
p = nodes[endpoint2].neigh;
while (p)
{
prev = p;
p = p->next;
}
p = (Tneigh *) alloc (sizeof(Tneigh));
prev->next = p;
p->who = endpoint1;
p->next = 0;
}
nodes[endpoint2].degree++;
}

for (i=0;i<numofnodes;++i)
{
nodecolors[i].mycolor = UNCOLORED;
nodecolors[i].neighcolored[RED] = 0;
nodecolors[i].neighcolored[BLUE] = 0;
}
}

int countcut ()
{
int i,cut;

cut =0;
for (i=0;i<numofnodes;++i)
if (nodecolors[i].mycolor == BLUE)
cut += nodecolors[i].neighcolored[RED];
return (cut);

}


//delete edge (endpoint1, endpoint2) where deg(endpoint1)=0
void delete_edge(int endpoint1, int endpoint2)
{
Tneigh *p, *pnext;
int found=0;

if (nodes[endpoint1].degree == 1)
nodes[endpoint1].neigh = 0;
nodes[endpoint1].degree--;

if (nodes[endpoint2].degree == 1)
nodes[endpoint2].neigh = 0;
else{
if (nodes[endpoint2].neigh->who == endpoint1)
nodes[endpoint2].neigh = nodes[endpoint2].neigh->next;
else
{
p=nodes[endpoint2].neigh;
while(!found){
pnext = p->next;
if (pnext->who == endpoint1){
found=1;
p->next = pnext->next;
}
else
p=p->next;
}
}
}
nodes[endpoint2].degree--;
}//delete_edge


void decimation()
{
Tneigh *p;
int i,j;

int endpoint1, endpoint2;
for (j=0; j<numofnodes; j++)
for (i=0;i<numofnodes;++i){
if (nodes[i].degree == 1) {
endpoint1 = i;
p=nodes[i].neigh;
endpoint2 = p->who;
delete_edge(endpoint1, endpoint2);
decimation_cut++;
}
}
}


//////////////////////////////////////////////////////////////////////////////
///////////////////////// Coloring Algorithm /////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
void color_ESA2006 ()
{
int i,j,n;
int discrepancy;
int max_discrepancy = -1;
int uncolored_degree;
int min_uncolored_degree = numofedges;
int numofcolorednodes = 0;

Tneigh *p;

for (i=0;i<numofnodes;++i)
{
nodecolors[i].mycolor = UNCOLORED;
nodecolors[i].neighcolored[RED] = 0;
nodecolors[i].neighcolored[BLUE] = 0;
}

while (numofcolorednodes < numofnodes)
{

//color all nodes with uncolored_degree=0
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED )
{
uncolored_degree = nodes[j].degree - nodecolors[j].neighcolored[BLUE] - nodecolors[j].neighcolored[RED];
if (uncolored_degree == 0) //color it now
{
n = j;
numofcolorednodes++;
//printf("%d \t color node %d with uncolored_degree %d \n", numofcolorednodes, n, uncolored_degree);
if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = BLUE;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[BLUE]++;
p=p->next;
}
}
else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = RED;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[RED]++;
p=p->next;
}
}
else
{
nodecolors[n].mycolor = randomnumber (2);
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
p=p->next;
}
}
}
}
}


// find an uncolored node with max discrepancy
max_discrepancy = -1;
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
{
discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
if (discrepancy > max_discrepancy)
{
n = j;
max_discrepancy = discrepancy;
}
}
}

//find an uncolored node with max_discrepancy having the minimun number of uncolored neighbors
min_uncolored_degree = numofedges;
for (j=0;j<numofnodes;++j)
{
if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
{
discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
if (discrepancy == max_discrepancy)
{
uncolored_degree = nodes[j].degree-nodecolors[j].neighcolored[RED]-nodecolors[j].neighcolored[BLUE];
if (uncolored_degree < min_uncolored_degree)
{
min_uncolored_degree = uncolored_degree;
n = j;
}
}

}
}

//color node n
if (nodecolors[n].mycolor == UNCOLORED && nodes[n].degree > 1)
{
numofcolorednodes++;
if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = BLUE;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[BLUE]++;
p=p->next;
}
}
else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
{
nodecolors[n].mycolor = RED;
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[RED]++;
p=p->next;
}
}
else
{
nodecolors[n].mycolor = randomnumber (2);
p=nodes[n].neigh;
while (p)
{
nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
p=p->next;
}
}
}
}
}




//////////////////////////////////////////////////////////////////////////////
////////////////////////////////// MAIN //////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
int main(int argc,char *argv[])
{

if (argc != 6) {
printf("Syntax: lb-sim [k] [dl] [du] [dstep] [output file name] \n");
exit(1);
}

srand( (unsigned)time( NULL ) );

k = atoi(argv[1]);
numofnodes = (int) pow(2,k);

dl = atof(argv[2]);
cl = 0.5*dl;

du = atof(argv[3]);
cu = 0.5*du;

dstep = atof(argv[4]);
cstep = 0.5*dstep;

d = dl;
c = 0.5*d;


while (c < cu + cstep)
{
numofedges = (int) (c*numofnodes);

initgraph ();

randomgraph ();

decimation_cut=0;
decimation ();

color_ESA2006 ();

printf ("n=%d \t d=%4.1f \t cut=%10.8f \n",
numofnodes, 2.0*c, (double) (countcut()+ decimation_cut) / (double) numofedges);

fp = fopen(argv[5], "a");

fprintf (fp, "n=%d \t d=%4.1f \t cut=%10.8f \n",
numofnodes, 2.0*c, (double) (countcut()+ decimation_cut) / (double) numofedges);

fclose(fp);

freegraph();

c = c + cstep;
}

return 0;
}//main




помогите реализоват это на паскале
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


я си не знаю.Как эта программа будет на паскале нужен исходник .
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name