Second winter vacation homework

Part#1 achievements

#include<iostream>
#include<math.h>
#include<fstream> 
using namespace std;
int i;
struct dataset
{
	long long ipin,ipout;
	long ptin,ptout;
	int ptcl=256;
}dt[10001];
struct ruleset
{
	int iip[5],oip[5];
	long long ipin,ipout;
	int smin,smout;
	int ptinlow,ptinup,ptoutlow,ptoutup; 
	char ptcl[10]={};
	int ptclmode,ptcll=256;
}rl[10001];
long long iptrans(int *ip)
{
	long long tmp=0,result=0;
	int a[4];
	a[0]=ip[0];a[1]=ip[1];a[2]=ip[2];a[3]=ip[3];
	for(int i=3;i>=0;i--)
	{
		tmp=0;
		for(int j=0;a[i]!=0;j++)
		{
			tmp+=((a[i]%2)*pow(10,j));
			a[i]/=2;
		}
		for(int j=0;tmp!=0;j++)	
		{
			result+=(tmp%10)*pow(2,j+(i*8));
			tmp/=10;
		}
	}
	return result;
}
long findrule(long n)
{
	for(long k=0;k<i;k++)
		{
			if(dt[n].ipin==rl[k].ipin&&dt[n].ipout==rl[k].ipout)
			{
	if(dt[n].ptin<=rl[k].ptinup&&dt[n].ptin>=rl[k].ptinlow&&dt[n].ptout<=rl[k].ptoutup&&dt[n].ptout>=rl[k].ptoutlow)
				{
					if(dt[n].ptcl==rl[k].ptcll||rl[k].ptclmode==1)
					{
						return k;
					}
				}
			}
		}
	return -1;
}
int main() 
{
	char tmp;
	
	fstream fin("rule.txt");
	
	for(i=0;!fin.eof();i++)
	{
		fin>>tmp>>	rl[i].iip[3]>>tmp>>rl[i].iip[2]>>tmp>>rl[i].iip[1]>>tmp>>rl[i].iip[0]>>tmp>>rl[i].smin;
		fin>>		rl[i].oip[3]>>tmp>>rl[i].oip[2]>>tmp>>rl[i].oip[1]>>tmp>>rl[i].oip[0]>>tmp>>rl[i].smout;
		fin>>rl[i].ptinlow>>tmp>>rl[i].ptinup>>rl[i].ptoutlow>>tmp>>rl[i].ptoutup;
		rl[i].ipin	=iptrans(rl[i].iip);
		rl[i].ipout	=iptrans(rl[i].oip);
		if(rl[i].ptcl[2]=='F'&&rl[i].ptcl[3]=='F')
		{
			rl[i].ptclmode=0;
			rl[i].ptcll=(((int)rl[i].ptcl[0])-48)*10+((int)rl[i].ptcl[1])-48;
		}
		else if(rl[i].ptcl[2]=='0'&&rl[i].ptcl[3]=='0')
		{
			rl[i].ptclmode=1;
		}
	}
	ifstream dfin("packet.txt");
	fstream fout("ans.txt");
	for(long j=0;;j++)
	{
		dfin>>dt[j].ipin>>dt[j].ipout>>dt[j].ptin>>dt[j].ptout>>dt[j].ptcl;
		if(dt[j].ptcl==256)
		{
			break;
		}
		else
		{
			fout<<findrule(j)<<endl;
		}
	}
	return 0;
}

I finally succeeded in writing a code that can be used normally.

The amount of code is not even 100 lines. Hey, hey~

However, of the 9191 data, only 8201 data are correct (after many tests, the correct data is always 8201). The correct rate is 89.2%. Most of the errors are that the judgment function returns "- 1" (there is no "- 1" in the correct answer!), Occasionally, a match is found but not the best match.

When testing the wrong data alone, the program can output 90% of the correct answers. It is not a question of judgement, but once again, it is a question of input, and no reason or solution has yet been found.

Part#2 repeat offer

The last mistake was fin get(rl[i].ptcl,10,'\n'); So I changed this sentence back to the basic fin sentence: fin > > TMP > > TMP > > RL [i] ptcl[0]>>rl[i]. ptcl[1]>>tmp>>tmp>>tmp>>rl[i]. ptcl[2]>>rl[i]. ptcl[3];
But then came the problem: fin EOF () did not run correctly. When opening a dataset with 9191 rows, 9192 rows were read in.
My solution is: since the protocol number ranges from 0 to 255, assign an initial value of 256 to the protocol number of each piece of data. When reading in normally, the initial value will be overwritten, and when reading in abnormally, it will not be overwritten ('\ 0' will not be overwritten). In this way, we can determine whether to judge and output this data.

In addition, I made the judgment code into a separate function findrule(j) to return the best match of the j-th data.

Part#3 can be improved

You can define only one row of the dataset, overwrite the contents of the previous row every time you read in a row, and judge and output the best match immediately after reading the data. Memory consumption can be greatly reduced.

In addition, my judgment algorithm is violent, and the theoretical time complexity is also high σ (n^2). Looking at the students' homework, I learned that some algorithms can also be used to reduce the time complexity. Let me study hard.